(articolo redatto da Domenico Di Mieri)
In questo approfondimento ti presentiamo un confronto tra algoritmi COMBINATORI per la generazione delle disposizioni con ripetizione di n elementi su k posizioni in c#.
Il problema di partenza
Sia N un insieme costituito da n elementi qualsiasi
N = { 1, 2, 3, 4 }, n = 4
Consideriamo un “registro” costituito da k postazioni ordinate in cui è possibile inserire uno qualsiasi degli elementi di N (es. per k = 5):
ki ∈N
Lo “stato” del registro è costituito dalla particolare configurazione dei valori di N scelti per ciascuna delle postazioni ki per ogni i da 1 a k.
Ad esempio:
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 2 |
| 1 | 1 | 1 | 1 | 3 |
| 1 | 1 | 1 | 1 | 4 |
| 1 | 1 | 1 | 2 | 1 |
| 1 | 1 | 1 | 2 | 2 |
| … | … | … | … | … |
| 4 | 4 | 4 | 4 | 4 |
Ma quanti sono gli stati differenti che può assumere il registro?
Immaginiamo di “separare” il registro considerandolo come composto da una sola postazione variabile ed un oggetto che può assumere un certo numero di configurazioni diverse:
La postazione k1 può assumere tutti i valori di N quindi il suo grado di variabilità è n.
Se l’oggetto a destra, cioè X, potesse assumere una sola configurazione allora l’intero registro composto da (k1, X) avrebbe lo stesso grado di variabilità di k1 cioè n.
Se, invece, X potesse assumere 2 disposizioni diverse (es. 0 e 1) allora potremmo avere le disposizioni
(k1, 0) e (k1, 1)
Dato che k1 può variare n volte è evidente che il registro potrebbe assumere 2 * n possibili disposizioni diverse.
Allo stesso modo se l’oggetto a destra potesse variare n volte allora avremmo n * n possibili disposizioni in totale.
Applicando lo stesso ragionamento “ricorsivamente” all’insieme X a destra si giunge facilmente a calcolare il numero di possibili configurazioni di un registro di k posizioni che possono assumere n valori è
C = nk
Nel nostro caso, ad esempio
C = 45 = 1024
Il caso più banale è considerare un registro costituito da 3 numeri decimali
n = 10 ovvero 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
k = 3
Il numero di possibili configurazioni è proprio 1000 = 103
Infatti avremmo
| 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 0 | 2 |
| … | … | … | |
| 10 | 0 | 0 | 9 |
| 11 | 0 | 1 | 0 |
| … | … | … | |
1000 | 9 | 9 | 9 |
Come possiamo generare disposizioni usando un linguaggio di programmazione, ad esempio C#?
Algoritmo con cicli for a codice
L’algoritmo più banale che possa venire in mente è costituito da k for innestati che ciclano su n elementi:
[code lang=”c”]for (int k1 = 0; k1 < n; k1++)
{
for (int k2 = 0; k2 < n; k2++)
{
for (int k3 = 0; k3 < n; k3++)
{
combinazione[p++] = new[] { k1, k2, k3 };
}
}
}
[/code]
Si osservi che la complessità computazionale dell’algoritmo è O(nk) quindi l’algoritmo è di tipo esponenziale e anche su macchine molto potenti, al crescere di k (ad esempio per k = 15) i tempi di calcolo iniziano ad essere scoraggianti.
L’algoritmo con i cicli for innestati scritti direttamente “a codice”:
- È il più veloce
- Non è possibile modificare a runtime il numero di cicli innestati.
Per superare lo svantaggio dei cicli innestati “prefissati” possiamo utilizzare la ricorsione.
Algoritmo ricorsivo
L’algoritmo ricorsivo consiste nel chiamare ricorsivamente la funzione sulla combinazione corrente.
Ad ogni passo di ricorsione si fissa per la posizione k uno degli n elementi e si ripete la la procedura sulla parte a destra.
La ricorsione termina quando non ci sono altri registri a destra.
Si noti che l’algoritmo ricorsivo, per la sua semplicità, è anche quello suggerito da ChatGPT.
[code lang=”c”]T[][] Combina<T>(T[] elementi, int numeroPosizioni)
{
int cnt = (int)Math.Pow(elementi.Length, numeroPosizioni);
List<T[]> disposizioni = new List<T[]>(cnt);
T[] combinazione = new T[numeroPosizioni];
Combina(disposizioni, combinazione, elementi, 0);
return disposizioni.ToArray();
}
void Combina<T>(
List<T[]> disposizioni,
T[] combinazione,
T[] elementi,
int k
)
{
if (k == combinazione.Length)
{
disposizioni.Add( (T[])combinazione.Clone() );
}
else
{
for (int i = 0; i < elementi.Length; i++)
{
combinazione[k] = elementi[i];
Combina(disposizioni, combinazione, elementi, k + 1);
}
}
}
[/code]
Questo algoritmo è molto veloce per valori di k piccoli ma le sue performance iniziano a degradarsi al crescere di k.
Un altro modo per generare le disposizioni consiste nel ricordare come abbiamo calcolato la variabilità del registro usando il concetto di oggetto X sconosciuto.
A ben vedere gli indici in ciascuna postazione seguono le stesse regole della somma con 1 sulla base 10, ma in questo caso la base è n ovvero la variabilità del registro.
In pratica consideriamo il registro come un valore espresso in base n, ogni unità “scorre” quando l’unità precedente è satura.
Algoritmo lineare
[code lang=”c”]
public class DisposizioniEnumerator<T> : IEnumerator<T[]>
{
private readonly T[] elementi;
private readonly int numeroPosizioni;
private int[] indici;
private int p;
public DisposizioniEnumerator (T[] elementi, int numeroPosizioni)
{
this.elementi = (T[])elementi.Clone();
this.numeroPosizioni = numeroPosizioni;
indici = new int[numeroPosizioni];
p = numeroPosizioni;
}
public bool MoveNext()
{
if (p == numeroPosizioni)
{
p -= 1;
return true;
}
else if (p < 0)
{
return false;
}
else
{
p = increment();
if (p < 0)
{
return false;
}
return true;
}
}
private int increment()
{
int i = numeroPosizioni – 1;
indici[i] += 1;
bool overflow = (indici[i] >= elementi.Length);
while (overflow)
{
for (int k = i; k < numeroPosizioni; k++)
{
indici[k] = 0;
}
i -= 1;
if (i < 0) break;
indici[i] += 1;
overflow = (indici[i] >= elementi.Length);
}
return i;
}
…
}
[/code]
Questo algoritmo ha il vantaggio di poter utilizzare un iteratore e, quindi, utilizzare meno memoria ed ha una velocità che per k superiore a 3 è quasi pari a quella dell’algoritmo con i cicli for.
Test degli algoritmi
Nel codice allegato, oltre ai file sorgente, sono forniti gli UnitTest ed i Benchmark per gli algoritmi illustrati.
Come si vede l’algoritmo più veloce è sempre quello con i cicli for inseriti direttamente a codice.
L’algoritmo ricorsivo ha performance che peggiorano al crescere del numero di postazioni.
L’algoritmo lineare, invece, ha performance stabili e abbastanza vicine a quelle ottenute con i cicli innestati.
Analisi delle performance
L’algoritmo ricorsivo è in generale meno performante dell’algoritmo “lineare” come si vede dalla tabella e dal grafico seguente:
Codice per i test
Il codice utilizzato in questo articolo è disponibile per il download alla pagina https://github.com/redazione-nexsoft/Disposizioni
Conclusioni
Che ne dici? Sei pronto a provare anche tu i codici che ti abbiamo proposto?
Se anche tu vuoi occuparti di progetti di ricerca e sviluppo IT di ultima generazione
dai un’occhiata alle nostre opportunità di lavoro e conosciamoci subito!
