Get all combinations of selecting k elements from an n-sized array

Question

Was asked this today in an interview. Didn't see it before, and spent quite a lot of time getting it to work (tricky with all the recursion).

The goal was to find all possible combinations of choosing k elements from a n-sized array (basically the Binomial coefficient) and return them.

Unlike this code - here I don't want all possible combinations, just those that are k in size. Permutations inside a k-size element are not counted (i.e. (1,2,3) == (2,1,3) == etc.).

The code assumes all elements in the array are unique (I guess it can be added to the basic sanity tests in the beginning, or handled in a way ).

The algorithm uses recursion, and some counter array (pushForward) to keep track of the permutations.

It works (At least in my tests).

Would be happy to hear if this can be simplified or made more efficient :-)

public class Combinations
{        
    private int[] _array; // holds the initial array; Assumed to contain different elements!!!
    private int _k; // the k elements needed to be chosen from that array
    private int[] _pushForward; // a kind of a counter to keep track how much we need to move forward each column
    private List<int[]> _results; // the results (all combinations); 
    private int[] _element; // the working element that is changed all the time

    public List<int[]> GetAllCombinations(int[] array, int k)
    {
        int len = array.Length;

        // basic sanity check
        if (len < k)
            throw new ArgumentException("Array length can't be less than number of selected elements");

        if (k < 1)
            throw new ArgumentException("Number of selected elements can't be less than 1");

        _array = array;
        _k = k;
        _results = new List<int[]>();
        _element = new int[k];
        _pushForward = new int[k]; // they are initialized to Zero already, no need to initialize again

        // the first element can move up to this position (in permutations); subsequent elements could move +1
        int maxStepsForward = len - _k + 1; 

        // entrance to recurssion method
        GetCombinations(0, maxStepsForward);

        return _results;
    }


    // col - the initial column handled in this recurse; can be between 0..k-1
    // maxSteps - correction for the max index; max index that this for loop can reach 
    private void GetCombinations(int col, int maxSteps)
    {
        for (int j = col + _pushForward[col]; j < maxSteps; j++)
        {
            // enter the corresponding column element
            _element[col] = _array[j]; 

            // if not in the last column enter recursion and move to next column
            if (col < _k - 1)
                GetCombinations(col + 1, maxSteps + 1);
            // else, just add the element
            else if (col == _k - 1)
            {
                // element is copied to new place in memory (shallow copy - works on ints) as working copy is constantly changed 
                int[] insert = new int[_k];
                _element.CopyTo(insert, 0);
                // new element is added to result list
                _results.Add(insert);
            }
        }
        // if we're out of the for loop, it means we finished a last-column cycle and need to push forward 
        // pushing forward is done for all elements in subsequent columns
        if (col > 0)
        {
            _pushForward[col - 1]++;
            for(int k = col; k < _k; k ++)
                _pushForward[k] = _pushForward[col - 1];
        }

    }
}

EDIT:

I have another way using bit operations, that is a bit less efficient I think, but maybe simpler... It uses a bitwise operation hack to check if the number of bits are equal to k elements (This can also be done less efficiently without the hack by converting the int to binary and then counting the 1's).

    public List<int[]> GetAllCombinationsUsingBits(int[] array, int k)
    {
        var result = new List<int[]>();
        var len = array.Length;           
        var total = Math.Pow(2, len);

        for (int i = 1; i < total; i++)
        {
            // could also be checked by counting the ones in the binary, though this will require moving the binary up
            if (numberOfSetBits(i) == k) 
            {
                var element = new int[k];
                var binary = Convert.ToString(i, 2);
                var bLen = binary.Length;
                if ( bLen < len)
                    binary = PrependZero(binary, len - bLen);

                int counter = 0;
                for (int j = 0; j < len; j++)
                {
                    if (binary[j] == '1')
                    {
                        element[counter] = array[j];
                        counter++;
                    }
                }
                result.Add(element);
            }
        }

        return result;
    }

    private string PrependZero(string binary, int i)
    {            
        for (int j = 0; j < i; j++)
            binary = "0" + binary;

        return binary;
    }

    private int numberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

Answer 1

Binomial coefficient \$\binom{n}{k}\$ is growing too fast (with \$n\$) to keep a list of all combinations in memory. I would suggest to use yield return instead.

---

The main improvement which can be done here - not to use Recursion at all.

Solution without recursion

static class Combinations
{
    // Enumerate all possible m-size combinations of [0, 1, ..., n-1] array
    // in lexicographic order (first [0, 1, 2, ..., m-1]).
    private static IEnumerable<int[]> CombinationsRosettaWoRecursion(int m, int n)
    {
        int[] result = new int[m];
        Stack<int> stack = new Stack<int>(m);
        stack.Push(0);
        while (stack.Count > 0)
        {
            int index = stack.Count - 1;
            int value = stack.Pop();
            while (value < n)
            {
                result[index++] = value++;
                stack.Push(value);
                if (index != m) continue;
                yield return (int[])result.Clone(); // thanks to @xanatos
                //yield return result;
                break;
            }
        }
    }

    public static IEnumerable<T[]> CombinationsRosettaWoRecursion<T>(T[] array, int m)
    {
        if (array.Length < m)
            throw new ArgumentException("Array length can't be less than number of selected elements");
        if (m < 1)
            throw new ArgumentException("Number of selected elements can't be less than 1");
        T[] result = new T[m];
        foreach (int[] j in CombinationsRosettaWoRecursion(m, array.Length))
        {
            for (int i = 0; i < m; i++)
            {
                result[i] = array[j[i]];
            }
            yield return result;
        }
    }
}

Benchmarking

[ClrJob(true)]
[RPlotExporter, RankColumn, MemoryDiagnoser]
public class CombinationBenchmark
{
    [Params(5, 6, 7, 8, 9, 10)]
    public int M;

    private readonly int[] _array = new int[20];

    [GlobalSetup]
    public void Setup()
    {
        Random r = new Random(123);
        for (int i = 0; i < _array.Length; i++)
        {
            _array[i] = r.Next();
        }
    }

    [Benchmark]
    public void CombinationsWoRecursion()
    {
        int s = 0;
        foreach (int[] i in Combinations.CombinationsRosettaWoRecursion(_array, M))
        {
            s += i[0];
        }
    }


    [Benchmark]
    public void CombinationsDavid()
    {
        int s = 0;
        CombinationsDavid c = new CombinationsDavid();
        foreach (int[] i in c.GetAllCombinations(_array, M))
        {
            s += i[0];
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        BenchmarkRunner.Run<CombinationBenchmark>();
    }
}

Results

I would like also highlight an extremely small memory footprint, which was achieved thanks to yield usage.

---

Another proposed solution is checking number of on-bits in \$2^{n}\$ numbers. By this, you are limiting your solution on \$n<=32\$ and doing \$2^{n}-\binom{n}{k}\$ checks for nothing.

Answer 2

public class Combinations
{        
    private int[] _array; // holds the initial array; Assumed to contain different elements!!!
    private int _k; // the k elements needed to be chosen from that array
    private int[] _pushForward; // a kind of a counter to keep track how much we need to move forward each column
    private List<int[]> _results; // the results (all combinations); 
    private int[] _element; // the working element that is changed all the time

    public List<int[]> GetAllCombinations(int[] array, int k)

This is rather un-object-oriented. The most OO way of doing this would be for Combinations to have a constructor which takes array (and possibly k, although arguments can be made either way). If you don't want to be OO, the exposed API method should be static and should not use fields to pass data to other methods.

I'm missing some documentation to say what assumptions are made about the contents of array. Can it contain duplicate values? Must it be ordered?

Why is the return value List<int[]>? I can see a strong argument for ISet<ISet<int>>, and also a strong argument for IEnumerable<ISet<int>> with lazy enumeration, but I can't see why the order of the combinations matters, or the order within a combination matters.

---

        // basic sanity check
        if (len < k)
            throw new ArgumentException("Array length can't be less than number of selected elements");

        if (k < 1)
            throw new ArgumentException("Number of selected elements can't be less than 1");

The sanity checks are reasonable, but why throw an exception? IMO the correct thing to do is to return an empty set of solutions.

---

        _pushForward = new int[k]; // they are initialized to Zero already, no need to initialize again

        // the first element can move up to this position (in permutations); subsequent elements could move +1
        int maxStepsForward = len - _k + 1; 

This is where I start getting confused. What are these two variables for?

    // col - the initial column handled in this recurse; can be between 0..k-1
    // maxSteps - correction for the max index; max index that this for loop can reach 
    private void GetCombinations(int col, int maxSteps)
    {
        for (int j = col + _pushForward[col]; j < maxSteps; j++)

Nope, still confused. It's not obvious to me why the algorithm is correct, which means that more comments are required.

---

            if (col < _k - 1)
                GetCombinations(col + 1, maxSteps + 1);
            // else, just add the element
            else if (col == _k - 1)

Not just else?

As a matter of taste, I prefer to have the special case dealt with inside the recursive call.

---

                // element is copied to new place in memory (shallow copy - works on ints) as working copy is constantly changed 
                int[] insert = new int[_k];
                _element.CopyTo(insert, 0);
                // new element is added to result list
                _results.Add(insert);

The last comment there is unnecessary, but the first one is helpful (and an important point).

---

The simpler way of implementing GetCombinations would be

    // Generate combinations recursively and add them to _results.
    // Each combination's indices are in increasing order.
    // Pre-condition: _element[0 .. col-1] select col indices in increasing order.
    private void GetCombinations(int col)
    {
        if (col == _k)
        {
             // _element holds indices which need to be mapped to _array
             int[] insert = new int[_k];
             for (int i = 0; i < _k; i++) insert[i] = _array[_element[i]];
             _results.Add(insert);
             return;
        }

        // To maintain the condition that the selected indices are in increasing order,
        // we must start with the index after the largest already selected one.
        int min = col == 0 ? 0 : _element[col - 1] + 1;
        for (_element[col] = min; _element[col] < _array.Length; _element[col]++)
        {
            GetCombinations(col + 1);
        }
    }

It can be improved by adding a sanity check that min isn't too high; and the evaluation of min can be removed by adding an extra parameter:

    // Generate combinations recursively and add them to _results.
    // Each combination's indices are in increasing order.
    // Pre-condition: _element[0 .. col-1] select col indices in increasing order.
    // Pre-condition: min is the smallest index which is larger than the selected ones.
    private void GetCombinations(int col, int min = 0)
    {
        if (col == _k)
        {
             // _element holds indices which need to be mapped to _array
             int[] insert = new int[_k];
             for (int i = 0; i < _k; i++) insert[i] = _array[_element[i]];
             _results.Add(insert);
             return;
        }

        // Since _element is in increasing order, we require _element[_k - 1] <= _array.Length - 1
        // By induction, we find that _element[_k - j] <= _array.Length - j
        // Substituting subst col = _k - j, j = _k - col:
        // _element[col] <= _array.Length - (_k - col)
        for (_element[col] = min; _element[col] < _array.Length + col - _k; _element[col]++)
        {
            GetCombinations(col + 1, _element[col] + 1);
        }
    }

Answer 3

I can't add to the existing reviews of your code (other than I find it a little hard to follow), but maybe you find the below Linq-approach useful as inspiration. It seems to be "slow" for small data sets but rather fast for larger:

public static IEnumerable<IEnumerable<T>> CombinationsOfK<T>(T[] data, int k)
{
  int size = data.Length;

  IEnumerable<IEnumerable<T>> Runner(IEnumerable<T> list, int n)
  {
    int skip = 1;
    foreach (var headList in list.Take(size - k + 1).Select(h => new T[] { h }))
    {
      if (n == 1)
        yield return headList;
      else
      {
        foreach (var tailList in Runner(list.Skip(skip), n - 1))
        {
          yield return headList.Concat(tailList);
        }
        skip++;
      }
    }
  }

  return Runner(data, k);
}

Usage:

  int[] data = Enumerable.Range(1, 10).ToArray();
  int k = 3;
    foreach (string comb in CombinationsOfK(data, k).Select(c => string.Join(" ", c)))
    {
      Console.WriteLine(comb);
    }