Creating all possible k combinations of n items in C++

Solution 1:

I assume you're asking about combinations in combinatorial sense (that is, order of elements doesn't matter, so [1 2 3] is the same as [2 1 3]). The idea is pretty simple then, if you understand induction / recursion: to get all K-element combinations, you first pick initial element of a combination out of existing set of people, and then you "concatenate" this initial element with all possible combinations of K-1 people produced from elements that succeed the initial element.

As an example, let's say we want to take all combinations of 3 people from a set of 5 people. Then all possible combinations of 3 people can be expressed in terms of all possible combinations of 2 people:

comb({ 1 2 3 4 5 }, 3) =
{ 1, comb({ 2 3 4 5 }, 2) } and
{ 2, comb({ 3 4 5 }, 2) } and
{ 3, comb({ 4 5 }, 2) }

Here's C++ code that implements this idea:

#include <iostream>
#include <vector>

using namespace std;

vector<int> people;
vector<int> combination;

void pretty_print(const vector<int>& v) {
  static int count = 0;
  cout << "combination no " << (++count) << ": [ ";
  for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
  cout << "] " << endl;
}

void go(int offset, int k) {
  if (k == 0) {
    pretty_print(combination);
    return;
  }
  for (int i = offset; i <= people.size() - k; ++i) {
    combination.push_back(people[i]);
    go(i+1, k-1);
    combination.pop_back();
  }
}

int main() {
  int n = 5, k = 3;

  for (int i = 0; i < n; ++i) { people.push_back(i+1); }
  go(0, k);

  return 0;
}

And here's output for N = 5, K = 3:

combination no 1:  [ 1 2 3 ] 
combination no 2:  [ 1 2 4 ] 
combination no 3:  [ 1 2 5 ] 
combination no 4:  [ 1 3 4 ] 
combination no 5:  [ 1 3 5 ] 
combination no 6:  [ 1 4 5 ] 
combination no 7:  [ 2 3 4 ] 
combination no 8:  [ 2 3 5 ] 
combination no 9:  [ 2 4 5 ] 
combination no 10: [ 3 4 5 ] 

Solution 2:

From Rosetta code

#include <algorithm>
#include <iostream>
#include <string>
 
void comb(int N, int K)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's
 
    // print integers and permute bitmask
    do {
        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]) std::cout << " " << i;
        }
        std::cout << std::endl;
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}
 
int main()
{
    comb(5, 3);
}

output

 0 1 2
 0 1 3
 0 1 4
 0 2 3
 0 2 4
 0 3 4
 1 2 3
 1 2 4
 1 3 4
 2 3 4

Analysis and idea

The whole point is to play with the binary representation of numbers for example the number 7 in binary is 0111

So this binary representation can also be seen as an assignment list as such:

For each bit i if the bit is set (i.e is 1) means the ith item is assigned else not.

Then by simply computing a list of consecutive binary numbers and exploiting the binary representation (which can be very fast) gives an algorithm to compute all combinations of N over k.

The sorting at the end (of some implementations) is not needed. It is just a way to deterministicaly normalize the result, i.e for same numbers (N, K) and same algorithm same order of combinations is returned

For further reading about number representations and their relation to combinations, permutations, power sets (and other interesting stuff), have a look at Combinatorial number system , Factorial number system

PS: You may want to check out my combinatorics framework Abacus which computes many types of combinatorial objects efficiently and its routines (originaly in JavaScript) can be adapted easily to many other languages.

Solution 3:

If the number of the set would be within 32, 64 or a machine native primitive size, then you can do it with a simple bit manipulation.

template<typename T>
void combo(const T& c, int k)
{
    int n = c.size();
    int combo = (1 << k) - 1;       // k bit sets
    while (combo < 1<<n) {

        pretty_print(c, combo);

        int x = combo & -combo;
        int y = combo + x;
        int z = (combo & ~y);
        combo = z / x;
        combo >>= 1;
        combo |= y;
    }
}

this example calls pretty_print() function by the dictionary order.

For example. You want to have 6C3 and assuming the current 'combo' is 010110. Obviously the next combo MUST be 011001. 011001 is : 010000 | 001000 | 000001

010000 : deleted continuously 1s of LSB side. 001000 : set 1 on the next of continuously 1s of LSB side. 000001 : shifted continuously 1s of LSB to the right and remove LSB bit.

int x = combo & -combo;

this obtains the lowest 1.

int y = combo + x;

this eliminates continuously 1s of LSB side and set 1 on the next of it (in the above case, 010000 | 001000)

int z = (combo & ~y)

this gives you the continuously 1s of LSB side (000110).

combo = z / x;
combo >> =1;

this is for 'shifted continuously 1s of LSB to the right and remove LSB bit'.

So the final job is to OR y to the above.

combo |= y;

Some simple concrete example :

#include <bits/stdc++.h>

using namespace std;

template<typename T>
void pretty_print(const T& c, int combo)
{
    int n = c.size();
    for (int i = 0; i < n; ++i) {
        if ((combo >> i) & 1)
            cout << c[i] << ' ';
    }
    cout << endl;
}

template<typename T>
void combo(const T& c, int k)
{
    int n = c.size();
    int combo = (1 << k) - 1;       // k bit sets
    while (combo < 1<<n) {

        pretty_print(c, combo);

        int x = combo & -combo;
        int y = combo + x;
        int z = (combo & ~y);
        combo = z / x;
        combo >>= 1;
        combo |= y;
    }
}

int main()
{
    vector<char> c0 = {'1', '2', '3', '4', '5'};
    combo(c0, 3);

    vector<char> c1 = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    combo(c1, 4);
    return 0;
}

result :

1 2 3 
1 2 4 
1 3 4 
2 3 4 
1 2 5 
1 3 5 
2 3 5 
1 4 5 
2 4 5 
3 4 5 
a b c d 
a b c e 
a b d e 
a c d e 
b c d e 
a b c f 
a b d f 
a c d f 
b c d f 
a b e f 
a c e f 
b c e f 
a d e f 
b d e f 
c d e f 
a b c g 
a b d g 
a c d g 
b c d g 
a b e g 
a c e g 
b c e g 
a d e g 
b d e g 
c d e g 
a b f g 
a c f g 
b c f g 
a d f g 
b d f g 
c d f g 
a e f g 
b e f g 
c e f g 
d e f g 

Solution 4:

In Python, this is implemented as itertools.combinations

https://docs.python.org/2/library/itertools.html#itertools.combinations

In C++, such combination function could be implemented based on permutation function.

The basic idea is to use a vector of size n, and set only k item to 1 inside, then all combinations of nchoosek could obtained by collecting the k items in each permutation. Though it might not be the most efficient way require large space, as combination is usually a very large number. It's better to be implemented as a generator or put working codes into do_sth().

Code sample:

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main(void) {

  int n=5, k=3;

  // vector<vector<int> > combinations;
 vector<int> selected;
 vector<int> selector(n);
 fill(selector.begin(), selector.begin() + k, 1);
 do {
     for (int i = 0; i < n; i++) {
      if (selector[i]) {
            selected.push_back(i);
      }
     }
     //     combinations.push_back(selected);
         do_sth(selected);
     copy(selected.begin(), selected.end(), ostream_iterator<int>(cout, " "));
     cout << endl;
     selected.clear();
 }
 while (prev_permutation(selector.begin(), selector.end()));

  return 0;
}

and the output is

0 1 2 
0 1 3 
0 1 4 
0 2 3 
0 2 4 
0 3 4 
1 2 3 
1 2 4 
1 3 4 
2 3 4 

This solution is actually a duplicate with Generating combinations in c++

Solution 5:

Here is an algorithm i came up with for solving this problem. You should be able to modify it to work with your code.

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

You can see an explanation of how it works here.