Pengindeksan k-kombinasi yang cepat

Saya meninjau kembali masalah lama yang saya kerjakan beberapa waktu lalu.

Skenario khas adalah "3 bit diatur dalam integer 8 bit", yaitu 00000111.

Semua kombinasi unik dengan 3 set bit dapat dengan mudah dihasilkan (dalam urutan) oleh loop bersarang. Yang saya tertarik adalah kombinasi pemetaan indeks <->, yaitu "00001011" akan menjadi kombinasi kedua (atau nilai "1" dalam indeks berbasis nol).

Sejauh ini, saya menjalankan semua kombinasi dan menyimpannya dalam sebuah tabel, menjadikan indeks pencarian -> percakapan sebagai operasi O (1). Arah lainnya adalah O (ln (n)) dengan pencarian dua bagian.

Kelemahannya adalah, ini jelas sangat berat pada memori jika kita meningkatkan domain, sampai pada titik di mana itu tidak layak.

Apa yang akan menjadi cara sederhana untuk menghitung kombinasi ke-n atau indeks untuk kombinasi yang diberikan? Urutan kombinasi akan menyenangkan, tetapi tidak wajib.

Menghasilkan kombinasi ke-n disebut algoritma "unranking". Perhatikan bahwa permutasi dan kombinasi sering dapat disamakan dengan cara masalah parameternya. Tanpa tahu persis apa masalahnya, sulit untuk merekomendasikan pendekatan yang tepat, dan pada kenyataannya, untuk sebagian besar masalah kombinatorik biasanya ada beberapa algoritma peringkat / penguraian kemungkinan yang berbeda.

Salah satu sumber yang bagus adalah "Algoritma Combinatorial" oleh Kreher dan Stinson. Buku ini memiliki banyak algoritma peringkat dan unranking yang baik dijelaskan dengan jelas. Ada sumber daya yang lebih maju, tetapi saya akan merekomendasikan Kreher sebagai titik awal. Sebagai contoh algoritma unranking pertimbangkan hal berikut:

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

Ini adalah permutasi unranking, tetapi seperti yang disebutkan di atas, dalam banyak kasus Anda dapat mengubah kombinasi unranking menjadi masalah permutasi yang setara.