Scroll Top
Via Antonio Amato, 20/22 84131 Salerno (SA)

Un confronto tra gli algoritmi combinatori in Csharp

Nexsoft blog | algoritmi combinatori

(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):

kiN

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:

11111
11112
11113
11114
11121
11122
44444

 

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

1000
2001
3002
10009
11010
1000
999
 

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:

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 };
			}
		}
}

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”:

  1. È il più veloce
  2. 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.

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);
          }
       }
}

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

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;
   }
   …           
}

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.

Nexsoft blog | algoritmi combinatori

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:

Nexsoft blog | test algoritmi combinatori
Nexsoft blog | algoritmi combinatori

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!

Questo sito utilizza cookies propri e si riserva di utilizzare anche cookie di terze parti per garantire la funzionalità del sito e per tenere conto delle scelte di navigazione.
Per maggiori dettagli e sapere come negare il consenso a tutti o ad alcuni cookie è possibile consultare la Cookie Policy.

USO DEI COOKIE

Se abiliti i cookie nella tabella sottostante, ci autorizzi a memorizzare i tuoi comportamenti di utilizzo sul nostro sito web. Questo ci consente di migliorare il nostro sito web e di personalizzare le pubblicità. Se non abiliti i cookie, noi utilizzeremo solo cookies di sessione per migliorare la facilità di utilizzo.

Cookie tecnicinon richiedono il consenso, perciò vengono installati automaticamente a seguito dell’accesso al Sito.

Cookie di statisticaVengono utilizzati da terze parti, anche in forma disaggregata, per la gestione di statistiche

Cookie di social networkVengono utilizzati per la condivisione di contenuti sui social network.

Cookie di profilazione pubblicitariaVengono utilizzati per erogare pubblicità basata sugli interessi manifestati attraverso la navigazione in internet.

AltriCookie di terze parti da altri servizi di terze parti che non sono cookie di statistica, social media o pubblicitari.