0

I want to implement an efficient non-recursive algorithm to generate combinations of size K from a set of size N in C++. So, basically if I have the following set of numbers [1, 2, 3, 4] then N = 4 and K = 2. This would give us the following set of numbers in the combination {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2} ... etc.

I don't want to generate the same set twice, so {1, 2} and {2, 1} are the same set.

My idea was to use the std::next_permutation from C++ and then if I look at just the first K elements of each permutation, then I have all possible combinations of size K from a set of size N.

Now this is highly inefficient because I generate N! permutations where most of the sets repeat : {1, 2} appears more than once because of the way permutations are generated.

Is there a very efficient way in C++ to generate these numbers from a set iteratively. I don't need to store the numbers anywhere I will only be looking at one combination at a time.

Mutating Algorithm
  • 2,604
  • 2
  • 29
  • 66
  • Is the set always going to be sorted? – Hill May 23 '16 at 19:33
  • @Hill Yes, the set is always sorted – Mutating Algorithm May 23 '16 at 19:35
  • There is a technique that uses arrays of bools to determine the next_combination. You basically call `next_permutation` on the array of bools, and wherever there is a "true", you output the corresponding entry in the set. – PaulMcKenzie May 23 '16 at 19:38
  • @PaulMcKenzie Do you have references / code ? – Mutating Algorithm May 23 '16 at 19:39
  • 1
    I wrote it years ago, trying to dig it up now, but I bet others here know of it. If you want to choose 2 items, you have an array of bools where you have 2 "true" values in the least-significant positions in the array (thus making it sorted). Then you call next_permutation on this array. Wherever you see a "true", that's what you output in your number array, so in other words, you have the bool array controlling what you select out of your number array. Doggone it, I had it, can't find it now. – PaulMcKenzie May 23 '16 at 19:42
  • @PaulMcKenzie I'm rooting for you to find it :P – Mutating Algorithm May 23 '16 at 19:43
  • 2
    I got [this](http://stackoverflow.com/a/25556248/2684539) for my part. – Jarod42 May 23 '16 at 19:43
  • 1
    Yep @Jarod42 has the goods. I guess my part is explaining on a high-level what's going on. Pay attention to: `if (bitset[i]) std::cout << v[i] << " ";` -- That's where you output the number corresponding to the "true" value. So those bools are going to move around each time `next_permutation` is called. – PaulMcKenzie May 23 '16 at 19:45
  • @DanMašek -- The first answer at that link makes my head spin. – PaulMcKenzie May 23 '16 at 19:53
  • 1
    @MutatingAlgorithm [Live Example](http://ideone.com/OWWYdv) – PaulMcKenzie May 23 '16 at 20:02

0 Answers0