Schnelle Indizierung von k-Kombinationen

Ich besuche ein altes Problem, an dem ich vor einiger Zeit gearbeitet habe.

Ein typisches Szenario ist "3 Bits werden innerhalb einer 8-Bit-Ganzzahl gesetzt", dh 00000111.

Alle eindeutigen Kombinationen mit 3 gesetzten Bits können leicht (in der Reihenfolge) durch verschachtelte Schleifen erzeugt werden. Was mich interessiert, ist die Mapping-Index-Kombination <->, dh "00001011" wäre die zweite Kombination (oder der Wert "1" in einem auf Null basierenden Index).

Bisher habe ich alle Kombinationen durchgearbeitet und in einer Tabelle gespeichert, sodass der Suchindex -> Konversation eine O (1) -Operation ist. Die andere Richtung ist O (ln (n)) mit Halbierungssuche.

Der Nachteil ist jedoch, dass dies offensichtlich den Speicher stark belastet, wenn wir die Domain bis zu einem Punkt vergrößern, an dem dies nicht mehr möglich ist.

Was wäre eine einfache Methode, um die n-te Kombination oder den Index für eine bestimmte Kombination zu berechnen? Die Reihenfolge der Kombinationen wäre schön, ist aber nicht obligatorisch.

Das Erzeugen der n-ten Kombination wird als "unranking" -Algorithmus bezeichnet. Beachten Sie, dass Permutationen und Kombinationen häufig durch die Parametrisierung des Problems gleichgesetzt werden können. Ohne genau zu wissen, was das Problem ist, ist es schwierig, den genau richtigen Ansatz zu empfehlen, und tatsächlich sind für die meisten kombinatorischen Probleme normalerweise mehrere unterschiedliche Ranking- / Unranging-Algorithmen möglich.

Eine gute Ressource sind "Combinatorial Algorithms" von Kreher und Stinson. Dieses Buch hat viele gute Ranking- und Unranking-Algorithmen, die klar erklärt wurden. Es gibt fortgeschrittenere Ressourcen, aber ich würde Kreher als Ausgangspunkt empfehlen. Betrachten Sie als Beispiel für einen Algorithmus ohne Rangfolge Folgendes:

/** 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;
}

Dies ist eine Permutation ohne Rangfolge. Wie oben erwähnt, können Sie in vielen Fällen eine Kombination ohne Rangfolge in ein äquivalentes Permutationsproblem umwandeln.