Daniel - 1 year ago 122
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.

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;
}
``````