Creating all possible k combinations of n items in C

Question

There are n people numbered from 1 to n  I have to write a code which produces and print all different combinations of k people from these n  Please explain the algorithm used for that

User · Answer

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

User · Answer

The basic idea of this solution is to mimic the way you enumerate all the combinations without repetitions by hand in high school  Let com be List int  of length k and nums be List int  the given n items  where n  gt   k  The idea is as follows  for x 0  in nums 0     n-1       for x 1  in nums idx of x 0    1    n-1          for x 2  in nums  idx of x 1    1     n-1                                 for x k-1  in nums  idx of x k-2  1     n-1   Obviously  k and n are variable arguments  which makes it impossible to write explicit multiple nested for-loops  This is where the recursion comes to rescue the issue  Statement len com    len nums i     gt   k checks whether the remaining unvisited forward list of items can provide k iitems  By forward  I mean you should not  walk the nums backward for avoiding the repeated combination  which consists of same set of items but in different order  Put it in another way  in these different orders  we can choose the order these items appear in the list by scaning the list forward  More importantly  this test clause internally prunes the recursion tree such that it only contains n choose k recursive calls  Hence  the running time is O n choose k   from typing import List  class Solution      def combine self  n  int  k  int  - gt  List List int            assert 1  lt   n  lt   20         assert 1  lt   k  lt   n         com sets              self  combine recurse k  list range 1  n 1        com sets          return com sets      def  combine recurse self  k  int  nums  List int   com  List int   com set  List List int              quot  quot  quot          O C n k           quot  quot  quot          if len com   lt  k              for i in range len nums                  Once again  don t com append   since com should not be global                  if len com    len nums i     gt   k                      self  combine recurse k  nums i 1    com    nums i    com set          else              if len com     k                  com set append com                  print com   sol   Solution   sol combine 5  3    1  2  3   1  2  4   1  2  5   1  3  4   1  3  5   1  4  5   2  3  4   2  3  5   2  4  5   3  4  5

User · Answer

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  lt iostream gt   include  lt vector gt   using namespace std   vector lt int gt  people  vector lt int gt  combination   void pretty print const vector lt int gt  amp  v      static int count   0    cout  lt  lt   combination no    lt  lt     count   lt  lt            for  int i   0  i  lt  v size      i    cout  lt  lt  v i   lt  lt           cout  lt  lt        lt  lt  endl     void go int offset  int k      if  k    0        pretty print combination       return        for  int i   offset  i  lt   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  lt  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

User · Answer

I have written a class in C  to handle common functions for working with the binomial coefficient  which is the type of problem that your problem falls under   It performs the following tasks    Outputs all the K-indexes in a nice format for any N choose K to a file   The K-indexes can be substituted with more descriptive strings or letters   This method makes solving this type of problem quite trivial  Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table   This technique is much faster than older published techniques that rely on iteration   It does this by using a mathematical property inherent in Pascal s Triangle   My paper talks about this   I believe I am the first to discover and publish this technique  Converts the index in a sorted binomial coefficient table to the corresponding K-indexes   I believe it is also faster than the other solutions  Uses Mark Dominus method to calculate the binomial coefficient  which is much less likely to overflow and works with larger numbers  The class is written in  NET C  and provides a way to manage the objects related to the problem  if any  by using a generic list   The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed   If this value is false  then it will not create the table   The table does not need to be created in order to perform the 4 above methods   Accessor methods are provided to access the table  There is an associated test class which shows how to use the class and its methods   It has been extensively tested with 2 cases and there are no known bugs    To read about this class and download the code  see Tablizing The Binomial Coeffieicent   It should be pretty straight forward to port the class over to C     The solution to your problem involves generating the K-indexes for each N choose K case   For example   int NumPeople   10  int N   TotalColumns     Loop thru all the possible groups of combinations  for  int K   N - 1  K  lt  N  K            Create the bin coeff object required to get all       the combos for this N choose K combination     BinCoeff lt int gt  BC   new BinCoeff lt int gt  N  K  false      int NumCombos   BinCoeff lt int gt  GetBinCoeff N  K      int   KIndexes   new int K      BC OutputKIndexes FileName  DispChars           60  false         Loop thru all the combinations for this N choose K case     for  int Combo   0  Combo  lt  NumCombos  Combo                  Get the k-indexes for this combination  which in this case          are the indexes to each person in the problem set        BC GetKIndexes Loop  KIndexes            Do whatever processing that needs to be done with the indicies in KIndexes                     The OutputKIndexes method can also be used to output the K-indexes to a file  but it will use a different file for each N choose K case

User · Answer

It can also be done using backtracking by maintaining a visited array   void foo vector lt vector lt int gt   gt   amp s vector lt int gt   amp data int go int k vector lt int gt   amp vis int tot         vis go  1      data push back go       if data size    k                s push back data           vis go  0      data pop back            return             for int i go 1 i lt  tot   i               if  vis i                       foo s data i k vis tot                      vis go  0      data pop back        vector lt vector lt int gt   gt  Solution  combine int n  int k       vector lt int gt  data     vector lt int gt  vis n 1 0      vector lt vector lt int gt   gt  sol     for int i 1 i lt  n   i              for int i 1 i lt  n   i  vis i  0     foo sol data i k vis n           return sol

User · Answer

To make it more complete  the following answer covers the case that the data set contains duplicate values  The function is written close to the style of std  next permutation   so that it is easy to follow up  template lt  class RandomIt  gt  bool next combination RandomIt first  RandomIt n first  RandomIt last      if  first    last    n first    first    n first    last          return false         RandomIt it left   n first    --it left    RandomIt it right   n first     bool reset   false    while  true          auto it   std  upper bound it right  last   it left        if  it    last              std  iter swap it left  it         if  reset                    it left          it right   it            it right          std  size t left len   std  distance it left  n first           std  size t right len   std  distance it right  last           if  left len  lt  right len                      std  swap ranges it left  n first  it right             std  rotate it right  it right left len  last                     else                     std  swap ranges it right  last  it left             std  rotate it left  it left right len  n first                           return true            else             reset   true        if  it left    first                  break                --it left        it right   n first              return false     The full data set is represented in the range  first  last   The current combination is represented in the range  first  n first  and the range  n first  last  holds the complement set of the current combination  As a combination is irrelevant to its order   first  n first  and  n first  last  are kept in ascending order to avoid duplication  The algorithm works by increasing the last value A on the left side by swapping with the first value B on the right side that is greater than A  After the swapping  both sides are still ordered  If no such value B exists on the right side  then we start to consider increasing the second last on the left side until all values on the left side are not less than the right side  An example of drawing 2 elements from a set by the following code    std  vector lt int gt  seq    1  1  2  2  3  4  5     do         for  int x   seq              std  cout  lt  lt  x  lt  lt   quot   quot             std  cout  lt  lt   quot  n quot       while  next combination seq begin    seq begin   2  seq end       gives  1 1 2 2 3 4 5  1 2 1 2 3 4 5  1 3 1 2 2 4 5  1 4 1 2 2 3 5  1 5 1 2 2 3 4  2 2 1 1 3 4 5  2 3 1 1 2 4 5  2 4 1 1 2 3 5  2 5 1 1 2 3 4  3 4 1 1 2 2 5  3 5 1 1 2 2 4  4 5 1 1 2 2 3   It is trivial to retrieve the first two elements as the combination result if needed

User · Answer

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  amp startNum  const unsigned int  amp bitVal  const unsigned int  amp testNum     Should be called with arguments  2 r -1  2  r-1   2  n-1        unsigned int n    startNum - bitVal   lt  lt  1      n    bitVal   1   0       for  unsigned int i   log2 testNum    1  i  gt  0  i--     Prints combination as a series of 1s and 0s         cout  lt  lt   n  gt  gt   i - 1   amp  1       cout  lt  lt  endl       if    n  amp  testNum   amp  amp  n    startNum          r nCr n  bitVal  testNum        if  bitVal  amp  amp  bitVal  lt  testNum          r nCr startNum  bitVal  gt  gt  1  testNum       You can see an explanation of how it works here

User · Answer

From Rosetta code  include  lt algorithm gt   include  lt iostream gt   include  lt string gt    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  lt  N    i      0  N-1  integers                       if  bitmask i   std  cout  lt  lt   quot   quot   lt  lt  i                    std  cout  lt  lt  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

User · Answer

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  lt vector gt   include  lt iostream gt   include  lt iterator gt   include  lt algorithm gt   using namespace std   int main void       int n 5  k 3        vector lt vector lt int gt   gt  combinations   vector lt int gt  selected   vector lt int gt  selector n    fill selector begin    selector begin     k  1    do        for  int i   0  i  lt  n  i            if  selector i                 selected push back i                              combinations push back selected            do sth selected        copy selected begin    selected end    ostream iterator lt int gt  cout              cout  lt  lt  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

User · Answer

Behind the link below is a generic C  answer to this problem  How to format all combinations out of a list of objects  You can limit the results only to the length of k pretty easily   https   stackoverflow com a 40417765 2613458

User · Answer

I thought my simple  quot all possible combination generator quot  might help someone  i think its a really good example for building something bigger and better you can change N  characters  to any you like by just removing adding from string array  you can change it to int as well   Current amount of characters is 36 you can also change K  size of the generated combinations  by just adding more loops  for each element  there must be one extra loop  Current size is 4  include lt iostream gt   using namespace std   int main     string num       quot 0 quot   quot 1 quot   quot 2 quot   quot 3 quot   quot 4 quot   quot 5 quot   quot 6 quot   quot 7 quot   quot 8 quot   quot 9 quot   quot a quot   quot b quot   quot c quot   quot d quot   quot e quot   quot f quot   quot g quot   quot h quot   quot i quot   quot j quot   quot k quot   quot l quot   quot m quot   quot n quot   quot o quot   quot p quot   quot q quot   quot r quot   quot s quot   quot t quot   quot u quot   quot v quot   quot w quot   quot x quot   quot y quot   quot z quot      for  int i1   0  i1  lt  sizeof num  sizeof string   i1          for  int i2   0  i2  lt  sizeof num  sizeof string   i2              for  int i3   0  i3  lt  sizeof num  sizeof string   i3                  for  int i4   0  i4  lt  sizeof num  sizeof string   i4                      cout  lt  lt  num i1   lt  lt  num i2   lt  lt  num i3   lt  lt  num i4   lt  lt  endl                                    Result 0  A A A 1  B A A 2  C A A 3  A B A 4  B B A 5  C B A 6  A C A 7  B C A 8  C C A 9  A A B      just keep in mind that the amount of combinations can be ridicules  --UPDATE-- a better way to generate all possible combinations would be with this code  which can be easily adjusted and configured in the  quot variables quot  section of the code   include lt iostream gt   include lt math h gt   int main           VARIABLES     char chars        A    B    C         int password 4  0          SIZES OF VERIABLES     int chars length   sizeof chars    sizeof char       int password length   sizeof password    sizeof int          CYCKLE TROUGH ALL OF THE COMBINATIONS     for  int i   0  i  lt  pow chars length  password length   i                       CYCKLE TROUGH ALL OF THE VERIABLES IN ARRAY         for  int i2   0  i2  lt  password length  i2                    IF VERIABLE IN  quot PASSWORD quot  ARRAY IS THE LAST VERIABLE IN CHAR  quot CHARS quot  ARRRAY             if  password i2     chars length                      THEN INCREMENT THE NEXT VERIABLE IN  quot PASSWORD quot  ARRAY                 password i2   1                       AND RESET THE VERIABLE BACK TO ZERO                 password i2    0                            PRINT OUT FIRST COMBINATION         std  cout  lt  lt  i  lt  lt   quot    quot           for  int i2   0  i2  lt  password length  i2                  std  cout  lt  lt  chars password i2    lt  lt   quot   quot                     std  cout  lt  lt   quot  n quot              INCREMENT THE FIRST VERIABLE IN ARRAY         password 0

[c++] Creating all possible k combinations of n items in C++

Examples related to c++

Examples related to algorithm

Examples related to math

Examples related to combinations

Examples related to combinatorics