Daniel - 1 year ago 122

C++ Question

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 Source

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