12

I'm revisiting an old problem that I was working on some time ago.

A typical scenario is "3 bits are set within an 8 bit integer", i.e. 00000111.

All unique combinations with 3 set bits can easily be generated (in order) by nested loops. What I'm interested in is the mapping index <-> combination, i.e. "00001011" would be the second combination (or value "1" in a zero-based index).

So far, I ran through all combinations and stored them in a table, making the look up index -> conversation a O(1) operation. The other direction is O(ln(n)) with bisect search.

The downside, however, is that this obviously is heavy on the memory if we increase the domain, up to a point where it's not feasible.

What would be a simple way to calculate the n.th combination or the index for a given combination? Order of combinations would be nice, but is not mandatory.

Improve this question
9
  • From Stack Overflow: What is the best way to loop through integers with at most k bits ON? and Bit hack to generate all integers with a given number of 1s
    – user40980
    Commented Jun 15, 2015 at 13:15
  • @MichaelT Your links do not address the question - iterating over the combinations is not the problem. This is about mapping indices and combinations. Given "11001000", what is the index (or enumeration count if you will)? What code belongs to index 1673?
    – Eiko
    Commented Jun 15, 2015 at 13:28
  • 1
    Ahh, in that case you might find OEIS useful. For example, the sequence 3,5,6,9,10,12,17,18 gives us sum of two distinct powers of two which is another way of saying "two bits on" in mathematical jargon. The various formulas there show various ways of computing the nth value.
    – user40980
    Commented Jun 15, 2015 at 13:35
  • 1
    8-bit integers have only 256 combinations of any bit patters which are trivial to store (and would take up less space than any clever code). What are your target / estimated bit counts?
    – 9000
    Commented Jun 15, 2015 at 18:10
  • 1
    As dug up elsewhere, this is known as a combinatorial number system, and Gosper's Hack can do it in O(1). The logic was done in HACKMEM 175 and is explained in this blog post (the original is quite terse).
    – user40980
    Commented Jun 15, 2015 at 18:25

1 Answer 1

Reset to default
4

Generating the n-th combination is called a "unranking" algorithm. Note that permutations and combinations can often equated by the way the problem is parameterized. Without knowing exactly what the problem is, it is difficult to recommend the exact right approach, and in fact, for most combinatoric problems there are usually several different ranking/unranking algorithms possible.

One good resource is "Combinatorial Algorithms" by Kreher and Stinson. This book has many good ranking and unranking algorithms clearly explained. There are more advanced resources, but I would recommend Kreher as a starting point. As an example of an unranking algorithm consider the following:

/** PKSUL : permutation given its rank, the slots and the total number of items
 *  A combinatorial ranking is number of the permutation when sorted in lexicographical order
 *  Example:  given the set { 1, 2, 3, 4 } the ctItems is 4, if the slot count is 3 we have:
 *     1: 123    7: 213   13: 312   19: 412
 *     2: 124    8: 214   14: 314   20: 413
 *     3: 132    9: 231   15: 321   21: 421
 *     4: 134   10: 234   16: 324   22: 423
 *     5: 142   11: 241   17: 341   23: 431
 *     6: 143   12: 243   18: 342   24: 432
 *  From this we can see that the rank of { 2, 4, 1 } is 11, for example. To unrank the value of 11:
 *       unrank( 11 ) = { 11 % (slots - digit_place)!, unrank( remainder ) }
 * @param rank           the one-based rank of the permutation
 * @param ctItems        the total number of items in the set
 * @param ctSlots        the number of slots into which the permuations are generated
 * @param zOneBased      whether the permutation array is one-based or zero-based
 * @return               zero- or one-based array containing the permutation out of the set { ctItems, 1,...,ctItems }
 */
public static int[] pksul( final int rank, final int ctItems, final int ctSlots, boolean zOneBased ){
    if( ctSlots <= 0 || ctItems <= 0 || rank <= 0 ) return null;
    long iFactorial = factorial_long( ctItems - 1 ) / factorial_long( ctItems - ctSlots );
    int lenPermutation = zOneBased ? ctSlots + 1 : ctSlots;
    int[] permutation = new int[ lenPermutation ];
    int[] listItemsRemaining = new int[ ctItems + 1 ];
    for( int xItem = 1; xItem <= ctItems; xItem++ ) listItemsRemaining[xItem] = xItem; 
    int iRemainder = rank - 1;
    int xSlot = 1;
    while( true ){
        int iOrder = (int)( iRemainder / iFactorial ) + 1;
        iRemainder = (int)( iRemainder % iFactorial );
        int iPlaceValue = listItemsRemaining[ iOrder ];
        if( zOneBased ){
            permutation[xSlot] = iPlaceValue;
        } else {
            permutation[xSlot - 1] = iPlaceValue;
        }
        for( int xItem = iOrder; xItem < ctItems; xItem++ ) listItemsRemaining[xItem] = listItemsRemaining[xItem + 1]; // shift remaining items to the left
        if( xSlot == ctSlots ) break;
        iFactorial /= ( ctItems - xSlot );
        xSlot++;
    }
    if( zOneBased ) permutation[0] = ctSlots;
    return permutation;
}

This is permutation unranking, but as mentioned above, in many cases you can convert a combination unranking into an equivalent permutation problem.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.