La generazione della n-esima combinazione è chiamata algoritmo "unranking". Nota che permutazioni e combinazioni possono essere spesso equiparate al modo in cui il problema è parametrizzato. Senza sapere esattamente quale sia il problema, è difficile raccomandare l'esatto approccio corretto, e infatti, per la maggior parte dei problemi combinatori ci sono di solito diversi algoritmi di ranking / unranking diversi.
Una buona risorsa è "Combinatorial Algorithms" di Kreher and Stinson. Questo libro ha molti buoni algoritmi di ranking e unranking chiaramente spiegati. Ci sono risorse più avanzate, ma raccomanderei Kreher come punto di partenza. Come esempio di un algoritmo unranking, considera quanto segue:
/** 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;
}
Questa è una permutazione unranking, ma come detto sopra, in molti casi è possibile convertire una combinazione che non si definisce in un problema di permutazione equivalente.