Generating successively the entire combination of a finite set using lexicographic order and bitwise arithmetic

Question

Consider the entire combination of length 3 of the next array of integer {1,2,3}.

I would like to go through the entire combination of length 3 using the following algorithm from wikipedia

// find next k-combination bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary { unsigned long u = x & -x; // extract rightmost bit 1; u = 0'00^a10^b unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b if (v==0) // then overflow in v, or x==0 return false; // signal that next k-combination cannot be represented x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a return true; // successful completion } 

What should be my initial value for this algorithm for all combinations {1,2,3}? When I get the result of the algorithm, how can I restore the combination?

I tried the following direct adaptation, but I am new to bitwise arithmetic, and I cannot say if this is correct.

 // find next k-combination, Java int next_combination(int x) { int u = x & -x; int v = u + x; if (v==0) return v; x = v +(((v^x)/u)>>2); return x; } 

Answer 1

I wrote a class to handle common functions for working with the binomial coefficient, which is the type of problem your problem relates to. It performs the following tasks:

• Prints all K-indices in a good format for any N that selects K to a file. K-indices can be replaced with more descriptive strings or letters. This method allows you to solve this type of problem is quite trivial.

• Converts K-indices to the corresponding record index in the table of sorted binomial coefficients. This method is much faster than older published iteration-based methods. He does this using the mathematical property inherent in the Pascal Triangle. My article talks about this. I believe that I am the first to discover and publish this technique, but I could be wrong.

• Converts an index into a sorted table of binomial coefficients into the corresponding K-indices. I believe this may be faster than the link you found.

• Uses the Mark Dominus method to calculate a binomial coefficient, which is much less likely to overflow and works with large numbers.

• The class is written in .NET C # and provides a way to manage the objects associated with the problem (if any) using a common list. The constructor of this class takes a bool value called InitTable, which, when true, will create a general list for storing objects to be managed. If this value is false, then it will not create a table. You do not need to create a table to complete the methods described above. To access the table, access methods are provided.

• There is a related test class that shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known errors.

To read about this class and download the code, see Tablizing the Binomial Coeffieicent .

You cannot convert this class to Java.

Answer 2

I found a class that exactly solves this problem. See CombinationGenerator Class here

https://bitbucket.org/rayortigas/everyhand-java/src/9e5f1d7bd9ca/src/Combinatorics.java

To restore the combination, do

 for(Long combination : combinationIterator(10,3)) toCombination(toPermutation(combination); 

Thank you all for your input.