Pagina personale di:
Carlo Vecchio
appunti di C#, R, SQL Server, ASP.NET, algoritmi, numeri
Vai ai contenuti

C# - Permutazioni e Combinazioni

C#

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



© 2020 Carlo Vecchio
Torna ai contenuti