Algoritmo per il calcolo diretto di combinazioni

Tweet

Come già detto nel precedente topic, le combinazioni, al pari delle permutazioni, rivestono un ruolo di primo piano nello sviluppo di molti software in quanto costituiscono la base di numerosi algoritmi.
Per tale motivo, in questo articolo descriveremo, come già fatto per le permutazioni, un metodo per il calcolo diretto di una specifica combinazione a partire dalla sua posizione nella lista delle combinazioni ordinate in modo lessicografico (ordine da dizionario).
Anche le combinazioni, analogamente alle permutazioni, possono essere costituite da elementi appartenenti agli insiemi più vari. Anche in questo caso, nel seguito, senza perdere di generalità, ci riferiremo a combinazioni i cui elementi sono numeri interi e, per comodità, ci riferiremo ad un caso specifico, fermo restando la validità del metodo nel caso generale.
Precisiamo, altresì, che nel seguito ci occuperemo esclusivamente delle combinazioni senza ripetizioni.
Allo scopo, ci riferiremo al caso delle combinazioni di 5 elementi presi 3 alla volta; ossia al caso n=5, k=3, in cui le combinazioni generate sono 10 e sono le seguenti:

0: [0, 1, 2]
1: [0, 1, 3]
2: [0, 1, 4]
3: [0, 2, 3]
4: [0, 2, 4]
5: [0, 3, 4]
6: [1, 2, 3]
7: [1, 2, 4]
8: [1, 3, 4]
9: [2, 3, 4]

In modo simile a quanto visto per le permutazioni, un ruolo fondamentale in tale algoritmo è svolto dal combinadic (detto anche sistema di numero combinatorio) di grado k; ossia un numero che mappa ogni indice in una nuova rappresentazione. Tale rappresentazione può essere calcolata individuando $c_1, c_2, ... c_k$ tale che ci è il più grande intero tale che $ci \choose i$<=index(i) dove index(k-1)=n-1, index(k-2)=index(k-1)-$c_{k-1} \choose k-2$, $\cdots$, index(1)=index(2)-$c_2 \choose 1$. Vediamo un esempio considerando il caso in esame e scegliendo index=4.

Il più grande intero $c_3$ tale che $c_3 \choose 3$<=4 è 4, il più grande intero $c_2$ tale che $c2 \choose 2$<=4-$4 \choose 3$=0 è 1, il più grande intero tale che $c_1 \choose 1$<=0 è 0; per cui si ha che per n=5, k=3 e index=4 il combinadic è [4, 1, 0].
Per il caso in esame, quindi, effettuando i calcoli per tutti gli indici compresi tra 0 e 9, otteniamo che la lista dei combinadic risulta essere la seguente:

0: [2, 1, 0]
1: [3, 1, 0]
2: [3, 2, 0]
3: [3, 2, 1]
4: [4, 1, 0]
5: [4, 2, 0]
6: [4, 2, 1]
7: [4, 3, 0]
8: [4, 3, 1]
9: [4, 3, 2]

Per vedere il legame tra il combinadic di un indice con la corrispondente combinazione, introduciamo il concetto di duale dell'indice che possiamo definire nel seguente modo:

dualIndex = $n \choose k$ - 1 - index

Per determinare la combinazione associata ad un dato indice, quindi, andiamo a considerare il combinadic del duale dell'indice e, detto ci il generico elemento del combinadic, poniamo:

$c_i$ = n-1-$c_i$ $\forall$ i=0,$\cdots$,k

Nel nostro caso, quindi, abbiamo che il duale dell'indice 4 è uguale a: 10-1-4 = 5 il cui combinadic è [4, 2, 0]. Da ciò segue che la combinazione associata è: [0, 2, 4].

Analogamente al caso delle permutazioni, l'algoritmo esposto è invertibile; ossia, a partire da una determinata combinazione è possibile calcolare il relativo combinadic e l'indice della combinazione. A differenza del caso precedente, però, per risalire all'indice della combinazione non è necessario calcolare necessariamente il combinadic; anzi, si può fare proprio l'inverso; ossia calcolare l'indice associato alla combinazione e da questi risalire al combinadic.
Lo snippet che consente di calcolare l'indice associato ad una determinata combinazione è il seguente:

int index = 0;
int j = 0;
for (int i = 0; i != k; ++i)
    for (++j; j != combination[i]; ++j)
        index += choose(n - j, k - i - 1);   // assume che ci sia una funzione choose(n, k) che restituisce il numero di combinazioni di n elementi presi a k la volta.

Anche questo algoritmo, come quello mostrato per le permutazioni, ha il notevole pregio di consentire l'immediata realizzazione di programmi paralleli per il calcolo di combinazioni.
Per il futuro, anche per esso, mi riservo di pubblicarne sul mio sito il codice sogente di un'implementazione Java.

Riferimenti Web:

http://msdn.microsoft.com/en-us/library/aa289166(v=vs.71).aspx

http://msdn.microsoft.com/en-us/magazine/cc163957.aspx

http://stackoverflow.com/questions/5307222/how-to-calculate-the-index-lexicographical-order-when-the-combination-is-given