Daniel Daniel - 2 months ago 11
C++ Question

Generate next combination of size k from integer vector

Lets say I have a vector of integers v = {0, 1,..., N-1} of size N.

for example: k = 2, N = 10
{0,1}, {0,2}, ..., {0,9}, {1,2}, ..., {8,9}


Given a size k, I want to generate all k-sized combinations of v.

But I want to do it one by one, using a method called NextCombination:

bool NextCombination(vector<int>& v, int k, int N){
if( is not the last combination){
turn v into it's next combination
return true;
}
return false;
}


that means, given the current state of v, the size k of the combination and the total number of elements, I'd like to change v (if possible) and return a bool indicating it was possible to get some next combination out of v.

I could not figure out how to make this without some boring recursions, and since this is just small problem of something I'm doing, I would like to figure out some smart/small solution to that.

Answer

MBo's answer involving std::next_permutation is better as far as readability is concerned.

However, that requires making an N-sized vector of 1s and 0s that you can do without if you really want to save on memory. The following solution essentially does the same thing in-place.

bool NextCombination(vector<int>& v, int k, int N) {
  // We want to find the index of the least significant element
  // in v that can be increased.  Let's call that index 'pivot'.
  int pivot = k - 1;
  while (pivot >= 0 && v[pivot] == N - k + pivot)
    --pivot;

  // pivot will be -1 iff v == {N - k, N - k + 1, ..., N - 1},
  // in which case, there is no next combination.
  if (pivot == -1)
    return false;

  ++v[pivot];
  for (int i = pivot + 1; i < k; ++i)
    v[i] = v[pivot] + i - pivot;
  return true;
}