Generate next combination of size k from integer vector

Question

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

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

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

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.

I mean if k = 2 and N = 4, i start with vector {0,1} and nextCombination will turn it into {0,2}, then into {0,3}, then {1,2}, then {1,3}, then {2,3} and lastly it returns false — Daniel
– Daniel, Commented Oct 4, 2016 at 5:36

Community · Accepted Answer · 2017-05-23 11:48:30Z

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

as i said, this is just a small problem (inside another bigger deal) and the readability of it doesn't matter as soon as it works well. this did the job, thanks!

MBo · Accepted Answer · 2016-10-04 05:55:33Z

You tagged C++, so the simplest approach for you - make vector length N, containing K ones and (N-K) zeros like {1,1,0,0,0} and apply std::next_permutation.

At every step positions of ones show - what numbers should be taken for combination.

For example, permutation {0,1,0,1,0} corresponds to (1,3) combination.

Edit

Code from Jörg Arndt's Matters Computational book using ready-to-use K-length array (bad formatting and readability)

 void first() { for (ulong k=0; k<k_; ++k) x_[k] = k; } ulong next() // Return smallest position that changed, return k with last combination { if ( x_[0] == n_ - k_ ) // current combination is the last { first(); return k_; } ulong j = k_ - 1; // easy case: highest element != highest possible value: if ( x_[j] < (n_-1) ) { ++x_[j]; return j; } // find highest falling edge: while ( 1 == (x_[j] - x_[j-1]) ) { --j; } // move lowest element of highest block up: ulong ret = j - 1; ulong z = ++x_[j-1]; // ... and attach rest of block: while ( j < k_ ) { x_[j] = ++z; ++j; } return ret; }

isn't there any way with the real values in K-sized vector (instead of N-sized binary vector) ? this way will turn my application slower by having to look more objects than necessary (for example, find 3 objects where N = 100 would not be good)

Collectives™ on Stack Overflow

Generate next combination of size k from integer vector

2 Answers 2

2 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Related