Indización rápida de combinaciones k

Estoy revisando un viejo problema en el que estaba trabajando hace algún tiempo.

Un escenario típico es "3 bits se establecen dentro de un entero de 8 bits", es decir, 00000111.

Todas las combinaciones únicas con 3 bits establecidos se pueden generar fácilmente (en orden) mediante bucles anidados. Lo que me interesa es la combinación de índice de mapeo <->, es decir, "00001011" sería la segunda combinación (o valor "1" en un índice basado en cero).

Hasta ahora, revisé todas las combinaciones y las almacené en una tabla, haciendo que el índice de búsqueda -> conversación sea una operación O (1). La otra dirección es O (ln (n)) con búsqueda bisecta.

La desventaja, sin embargo, es que esto obviamente es pesado en la memoria si aumentamos el dominio, hasta un punto donde no es factible.

¿Cuál sería una manera simple de calcular la combinación n.th o el índice para una combinación dada? El orden de las combinaciones sería bueno, pero no es obligatorio.

La generación de la enésima combinación se denomina algoritmo "sin clasificación". Tenga en cuenta que las permutaciones y combinaciones a menudo pueden equipararse por la forma en que se parametriza el problema. Sin saber exactamente cuál es el problema, es difícil recomendar el enfoque correcto exacto, y de hecho, para la mayoría de los problemas combinatorios generalmente hay varios algoritmos diferentes de clasificación / desorganización posibles.

Un buen recurso es "Algoritmos combinatorios" de Kreher y Stinson. Este libro tiene una buena clasificación y algoritmos de clasificación claramente explicados. Hay recursos más avanzados, pero recomendaría Kreher como punto de partida. Como ejemplo de un algoritmo de clasificación, considere lo siguiente:

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

Esta es la clasificación de permutación, pero como se mencionó anteriormente, en muchos casos puede convertir una combinación de clasificación en un problema de permutación equivalente.