C# - Permutazioni e Combinazioni
Le permutazioni
• Dato un insieme di n elementi, le permutazioni sono tutti i diversi insiemi degli stessi n elementi. Per esempio se l’insieme è fatto dai quattro elementi {cane, gatto, cavallo, elefante}, ci sono 24 permutazioni: {cane, gatto, cavallo, elefante}, {cane, gatto, elefante, cavallo}, … ed altre 22.
• Il numero di permutazioni di un insieme di n elementi è semplicemente il fattoriale di n (che si indica con n!). Questo fatto lo si trova facilmente tenendo conto che ci sono n possibili elementi in prima posizione, n-1 possibili elementi in seconda posizione, n-2 possibili elementi in terza posizione e così via, fino a un possibile elemento in ultima posizione.
Lista ordinata delle permutazioni
• La funzione seguente, accetta in input un array di int[] (che è l'insieme degli elementi dei quali si vogliono le permutazioni) e dà in uscita una lista di int[] (dove ogni elemento della lista è una diversa permutazione).
• L'elenco ottenuto è in ordine lessicografico.
• Nel caso si vogliano le permutazioni di una lista di elementi diversi da numeri interi (per esempio stringhe), basta inserirli in una lista o un array e permutare i numeri da 0 a N: ogni permutazione conterrà così l'elenco degli indici della lista o dell'array che contiene gli elementi da permutare.
• Questa funzione utilizza la funzione Fattoriale() che si trova qua: link.
private static List<int[]> Permutations(int[] data)
{
// Array di ritorno
List<int[]> ret = new List<int[]>();
// Si aggiunge la prima e si generano tutte le altre
ret.Add( (int[]) data.Clone() );
if (data.Length <= 1)
return ret;
int numPermutazioni = Fattoriale(data.Length);
for (int k = 0; k < numPermutazioni - 1; k++)
{
int i = data.Length - 1;
while (data[i - 1] >= data[i])
i--;
int j = data.Length;
while (data[j - 1] <= data[i - 1])
j--;
// Scambia data[i - 1] <--> data[j - 1]
int temp = data[i - 1];
data[i - 1] = data[j - 1];
data[j - 1] = temp;
i++;
j = data.Length;
while (i < j)
{
// Scambia data[i - 1] <--> data[j - 1]
temp = data[i - 1];
data[i - 1] = data[j - 1];
data[j - 1] = temp;
i++;
j--;
}
ret.Add((int[])data.Clone());
}
return ret;
}
• Esempio:
// Permutazioni dei numeri 1, 3, 5 e 7
int[] data = new int[4] {1, 3, 5, 7};
List<int[]> res = Permutations(data);
// Risultato
for (int i = 0; i < res.Count; i++)
{
for (int j = 0; j < res[i].Length; j++)
{
Console.Write(res[i][j] + " ");
}
Console.WriteLine("");
}
• Output:
1 3 5 7
1 3 7 5
1 5 3 7
1 5 7 3
1 7 3 5
1 7 5 3
3 1 5 7
3 1 7 5
3 5 1 7
3 5 7 1
3 7 1 5
3 7 5 1
5 1 3 7
5 1 7 3
5 3 1 7
5 3 7 1
5 7 1 3
5 7 3 1
7 1 3 5
7 1 5 3
7 3 1 5
7 3 5 1
7 5 1 3
7 5 3 1
Estrazione di una specifica permutazione
• In alcuni casi non è necessario estrarre tutte le permutazioni di un insieme, ma solo una.
• La funzione seguente estrae una sola permutazione tra tutte le permutazioni possibili. Per esempio in un insieme di 4 elementi, ci sono 4! = 24 permutazioni. Se si elencano le permutazioni in ordine lessicografico, considerando come elementi i numeri da 0 a 3 (perciò 4 elementi) si hanno le seguenti permutazioni ordinate:
0 1 2 3 -> indice 0
0 1 3 2 -> indice 1
0 2 1 3 -> indice 2
0 2 3 1 -> indice 3
0 3 1 2 -> indice 4
0 3 2 1 -> indice 5
1 0 2 3 -> indice 6
1 0 3 2 -> indice 7
....... ........
3 2 1 0 -> indice 23
• La funzione accetta in input due parametri. Il primo è l'indice della permutazione richiesta (da 0 a N-1), il secondo è la dimensione dell'insieme sul quale viene calcolata la premutazione.
• La funzione utilizza anche un'altra funzione chiamata Factoradic() della quale è riportato il codice.
private static int[] Permutation(int index, int elements)
{
int[] ret = new int[elements];
int[] temp = new int[elements];
int[] factoradic = Factoradic(index, elements);
// Calcola la permutazione di indice 'index' (da 0 a max-1) in un insieme di 'elements' elementi,
for (int i = 0; i < elements; i++)
temp[i] = i;
for (int i = 0; i < elements; i++)
{
ret[i] = temp[factoradic[i]];
// Anziché rimuovere l'elemento, si spostano tutti quelli di indice successivo
// (che non saranno più usati)
for (int j = factoradic[i]; j < temp.Length - 1; j++)
{
temp[j] = temp[j + 1];
}
}
return ret;
}
private static int[] Factoradic(int number, int elements)
{
int[] ret = new int[elements];
for (int i = 1; i <= elements; ++i)
{
ret[elements - i] = number % i;
number /= i;
}
return ret;
}
• Esempio:
// Calcolo della permutazione 7 di un insieme di quattro elementi
int[] res = Permutation(7, 4);
// Risultato
for (int i = 0; i < res.Length; i++)
{
Console.Write(res[i] + " ");
}
• Output:
1 0 3 2
Lista ordinata delle combinazioni
• Quando si parla di combinazioni, si parla di insiemi di N elementi presi a gruppi di K.
• Dati i numeri N e K, la funzione seguente dà in uscita una lista di int[] (dove ogni elemento della lista è una diversa combinazione).
• L'elenco ottenuto è in ordine lessicografico.
• Il numero di combinazioni di un insieme di N elementi presi a gruppi di K è N!/K!(N-K)!.
• Nel caso si vogliano le permutazioni di una lista di elementi diversi da numeri interi (per esempio stringhe), basta inserirli in una lista o un array e calcolare le combinazioni volute. Ogni combinazione conterrà così gli indici della lista o dell'array che contiene gli elementi da permutare.
private static List<int[]> Combinations(int n, int k)
{
// Gli n elementi sono i numeri da 0 a n-1.
// In C(5, 3), prima combinazione è comb[0, 1, 2]; ultima combinazione è [2, 3, 4].
List<int[]> ret = new List<int[]>();
int[] comb = new int[k]; // Combinazione generica
int[] combMax = new int[k]; // Ultima combinazione
if (n == 0)
return ret;
if (k == 0)
return ret;
if (n < k)
return ret;
// Se l'elemento mobile è l'ultimo degli elementi
// (è mobile di sicuro perché è l'ultimo, quindi può essere spostato)
// Allora aumenta l'indice di 1.
// Altrimenti aumenta l'indice di 1 e imposta tutti gli altri elementi negli indici consecutivi
// Posizione iniziale
for (int i = 0; i < k; i++)
{
comb[i] = i;
}
// È la prima soluzione
ret.Add((int[]) comb.Clone());
// Calcolo dell'ultima soluzione
for (int i = 0; i < k; i++)
{
combMax[i] = n - k + i;
}
while (true)
{
// C(5, 3)
// 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]
// Nella combinazione attuale, si cerca l'indice incrementabile più alto.
bool trovatoIncrementabile = false;
int indiceIncrementabile = -1;
for (int i = k - 1; i >= 0; i--)
{
// Se l'indice è l'ultimo, basta verificare che sia inferiore al massimo che può assumere
if (i == k - 1)
{
if (comb[i] < combMax[i])
{
// Trovato ed è l'ultimo elemento
trovatoIncrementabile = true;
indiceIncrementabile = i;
break;
}
}
// Altrimenti basta verificare che se fosse incrementato,
// non sia uguale all'elemento successivo della combinazione
else
{
if (comb[i] < combMax[i] && comb[i] + 1 != comb[i + 1])
{
// Trovato ed è l'ultimo elemento
trovatoIncrementabile = true;
indiceIncrementabile = i;
break;
}
}
}
// Se non trovato nessun valore incrementabile, l'algoritmo è finito
if (!trovatoIncrementabile)
{
break;
}
// A questo punto, ho trovato un indice incrementabile
// In ogni caso lo si incrementa
comb[indiceIncrementabile]++;
// Se non è l'ultimo, si posizionano gli altri indici nelle posizioni successive
if (indiceIncrementabile != k - 1)
{
for (int i = indiceIncrementabile + 1; i < k; i++)
{
comb[i] = comb[i - 1] + 1;
}
}
// Nuova combinazione
ret.Add((int[])comb.Clone());
}
return ret;
}
• Esempio:
// Calcolo di tutte le combinazioni di un insieme di 5 elementi a gruppi di 3
List<int[]> res = Combinations(5, 3);
// Risultato
for (int i = 0; i < res.Count; i++)
{
for (int j = 0; j < res[i].Length; j++)
{
Console.Write(res[i][j] + " ");
}
Console.WriteLine("");
}
• Output:
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4