Il metodo shuffle in C#

In Python esiste il metodo shuffle che permette di “mischiare” il contenuto di una lista (vedi www.w3schools.com/python/ref_random_shuffle.asp); in ambiente C# questo metodo non esiste ma è facilmente implementabile, vediamo come fare...

Qualche giorno fa sono stato contattato da un nuovo amico, Luigi, che mi chiedeva se potevo preparagli un programma per estrarre una serie di numeri da giocare al Superenalotto. In sostanza, Luigi mi chiedeva un programma Windows per estrarre “n” numeri, senza ripetizioni, presi dall'insieme dei valori da 1 a 90.

Luigi aveva bisogno di un programma Windows che potesse girare anche da chiavetta USB, ovvero senza bisogno di installazione; è per questo motivo che ho scelto C#, nonostante volessi usare Python!

L’implementazione è stata molto semplice, in pratica ho “simulato” l’estrazione dei numeri da una lista precaricata con i 90 numeri, popolando una nuova lista con i soli numeri estratti.

public static List<int> LotteryExtraction(List<int> source, int nextract)
{
     Random rnd = new Random();
     List<int> extr = new List<int>();
     int i;
     int idx;

     for(i=0; i<nextract; i++)
     {
          idx = rnd.Next(0, source.Count); // lower bound inclusive, upper bound exclusive
          extr.Add(source[idx]);
          source.RemoveAt(idx);
     }
     return extr;
}

La funzione LotteryExtraction() riceve in input la lista di interi source, che il chiamante deve caricare con i numeri da 1 a 90, e l'indicazione di quanti numeri estrarre in nexctract; in output, la funzione ritorna una lista dei numeri estratti da source. Il funzionamento dovrebbe essere abbastanza evidente, con il ciclo che estrae i numeri dalla lista, in maniera casuale, e li inserisce nella lista extr che verrà ritornata alla fine. Per l'estrazione casuale uso il metodo Next() per ottenere un valore compreso fra 0 e source.Count-1 (source.Count decresce ad ogni estrazione), da usare come indice per prelevare e rimuovere da source.

Si tratta di una funzione scritta velocemente, alcune migliorie potrebbero essere:
a) caricare la lista source direttamente all'interno della funzione, senza bisogno di farcela passare;
b) controllare che il parametro nextract non richieda l'estrazione di più elementi di quanti ce ne siano nella lista di partenza.

E veniamo al dunque ...

Pensando all'implementazione che ne avrei fatto in Python, dove avrei probabilmente utilizzato il metodo shuffle per mischiare i numeri e poi stampare i primi "n" valori della lista mischiata, ho voluto fare una ricerca su Internet, anche per capire se ci fosse una soluzione più elegante rispetto alla mia.

Ho trovato questa discussione molto interessante https://stackoverflow.com/questions/273313/randomize-a-listt. Tra i vari interventi vi sono alcune implementazioni del metodo shuffle; la prima è questa qui sotto:

public static List<int> Shuffle(List<int> source)
{
     Random rnd = new Random();
     return source.OrderBy(((item) => rnd.Next())).ToList();
}

In pratica viene richiamato il metodo OrderBy() utilizzando come parametro di ordinamento un valore casuale; per capire il funzionamento si può immaginare di assegnare ad ogni elemento della lista (ovvero ad ogni numero da 1 a 90) un valore casuale, per poi riordinare la lista in base a tale valore.

Un'altra implementazione molto interessante è quella che fa uso dell'algoritmo Fisher & Yates, spiegato qui https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

public static void ShuffleFisherYates(List<int> list)
{
     Random rnd = new Random();
     int n = list.Count;
     int k, val;
     
     while (n > 1)
     {
         n--;
         k = rnd.Next(n + 1);
         val = list[k];
         list[k] = list[n];
         list[n] = val;
     }
}

Si tratta di un ciclo che esegue in loco il rimescolamento (una descrizione più dettagliata la potete trovare su wikipedia).

Se volete provare anche voi queste funzioni, le potete trovare già implementate all'interno del programma GeneraCo che ho aggiunto nella sezione Download di questo sito; se poi volete solo utilizzare il programma, per generare colonne da giocare... buon divertimento!!!