Indexação rápida de combinações k

11

Estou revisitando um problema antigo em que estava trabalhando há algum tempo.

Um cenário típico é "3 bits são definidos em um número inteiro de 8 bits", ou seja, 00000111.

Todas as combinações exclusivas com 3 bits definidos podem ser facilmente geradas (em ordem) por loops aninhados. O que me interessa é a combinação do índice de mapeamento <->, ou seja, "00001011" seria a segunda combinação (ou o valor "1" em um índice baseado em zero).

Até agora, examinei todas as combinações e as armazenei em uma tabela, tornando o índice de consulta -> conversação uma operação O (1). A outra direção é O (ln (n)) com a busca bissética.

A desvantagem, no entanto, é que isso obviamente pesa muito na memória se aumentarmos o domínio, até um ponto em que isso não seja viável.

Qual seria uma maneira simples de calcular a n.ésima combinação ou o índice de uma dada combinação? A ordem das combinações seria legal, mas não é obrigatória.

algorithms combinatorics Eiko
fonte
Do estouro de pilha: Qual é a melhor maneira de fazer um loop através de números inteiros com no máximo k bits ON? e Bit cortar para gerar todos os inteiros com um determinado número de 1s
@ MichaelT Seus links não tratam da questão - iterar sobre as combinações não é o problema. Trata-se de mapear índices e combinações. Dado "11001000", qual é o índice (ou contagem de enumeração, se você desejar)? Qual código pertence ao índice 1673?
Eiko
1
Ahh, nesse caso, você pode achar o OEIS útil. Por exemplo, a sequência 3,5,6,9,10,12,17,18 nos dá a soma de dois poderes distintos de dois, que é outra maneira de dizer "dois bits" no jargão matemático. As várias fórmulas mostram várias maneiras de calcular o enésimo valor.
1
Inteiros de 8 bits têm apenas 256 combinações de padrões de bits que são triviais para armazenar (e ocupariam menos espaço do que qualquer código inteligente). Qual é a sua meta / contagem de bits estimada?
9000
1
Como desenterrado em outro lugar, isso é conhecido como sistema combinatório de números , e o Gosper's Hack pode fazê-lo em O (1). A lógica foi feita no HACKMEM 175 e é explicada nesta postagem do blog (o original é bastante conciso).

Respostas:

3

A geração da n-ésima combinação é chamada de algoritmo "sem classificação". Observe que permutações e combinações geralmente podem ser equiparadas pela maneira como o problema é parametrizado. Sem saber exatamente qual é o problema, é difícil recomendar a abordagem exata exata e, de fato, para a maioria dos problemas combinatórios, geralmente existem vários algoritmos diferentes de classificação / desarticulação possíveis.

Um bom recurso é "Algoritmos Combinatórios", de Kreher e Stinson. Este livro tem muitos bons algoritmos de classificação e desclassificação claramente explicados. Existem recursos mais avançados, mas eu recomendaria o Kreher como ponto de partida. Como exemplo de um algoritmo de desclassificação, considere o seguinte:

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

Isso é desregulamentação da permutação, mas, como mencionado acima, em muitos casos, você pode converter uma desorganização da combinação em um problema de permutação equivalente.

Tyler Durden
fonte