Qualche settimana fa sono stato contattato da un nuovo amico di nome Vincenzo che era alla ricerca di un archivio con tutte le 622.614.630 combinazioni possibili del superenalotto.

lotto 540 300

Un bel sabato pomeriggio mi arriva questo messaggio, proveniente dalla pagina dei contatti di questo sito, da un nuovo amico di nome Vincenzo:

Ciao, ho letto il tuo articolo in cui parli di aver sviluppato un algoritmo per ottenere le combinazioni. [...] e ho bisogno di ottenere tutte le combinazioni del superenalotto (che sono 622.614.630). Potresti aiutarmi?

Nota: Vincenzo probabilmente si riferiva a questo articolo "Algoritmo per la ricerca delle combinazioni".

L'idea di generare un file con tutte le combinazioni mi ha inizialmente spaventato: di certo avrei avuto poi il problema di dover trasferire un file di dimensioni consistenti. L'unica possibilità era di predisporre un programma in modo da permettere a Vincenzo di generare da solo le combinazioni, sul proprio PC.

PROVA CON PYTHON

Qualche giorno dopo, per farmi un'idea, ho provato con Python a generare tutte queste combinazioni, riprendendo le esperienze che potete trovare qui "Combinazioni e permutazioni in Python"; ho lanciato IDLE e ho iniziato con:

import itertools 

per importare il modulo itertools che contiene la funzione combinations(), per la generazione di combinazioni; quindi ho dato:

o=itertools.combinations(range(1,91),6)

ma poi volendo trasformare l'oggetto in una lista ho ottenuto:

lst=list(o)
Traceback (most recent call last):
File "<pyshell#4>", line 1, in <module>
lst=list(o)
MemoryError

E' chiaro che non si può passare tramite la lista; se proprio avessi voluto utilizzare Python avrei dovuto lavorare direttamente con l'oggetto ritornato da combinations(), in questo modo:

for x in o:
print(x)

provare per credere (se volete interrompere l'esecuzione basta dare CTRL-C)!!!

PROGRAMMA IN C

Rendendomi conto del numero elevato di combinazioni (ma per questo non c'era bisogno della prova con Python!) e quindi della possibilità concreta che la creazione dell'archivio potesse durare anche giorni (considerando che dovevo anche salvare su file) mi sono imposto che:
- nel programma di creazione era necessario poter creare archivi parziali, ad esempio le combinazioni che iniziano con un certo numero;
- il programma lo avrei scritto in C, modificando il codice presente in questo articolo "Algoritmo per la ricerca delle combinazioni" e predisponendo una semplice interfaccia grafica per l'impostazione dei parametri di lavoro.

Generare un archivio parziale ha diversi vantaggi:
- quello di poter lanciare l'estrazione su più postazioni contemporaneamente, se si hanno più postazioni a disposizione;
- quello di poter lanciare le estrazioni in momenti diversi;
- quello di poter verificare i risultati della procedura se l'estrazione è sufficientemente limitata.

L'idea di selezionare il numero iniziale mi è sembrata subito una buona idea; qui sotto riporto un estratto del foglio di calcolo in cui ho determinato il numero di possibili combinazioni per ciascun "numero iniziale".
In pratica si tratta del calcolo del numero di combinazioni di n elementi su k posizioni dove n corrisponde a 90-"numero iniziale" mentre k è 5 (per i 5 numeri che seguono il numero iniziale).

Num.Iniziale n k Combinazioni
1 89 5 41.507.642
2 88 5 39.175.752
3 87 5 36.949.857
4 86 5 34.826.302
80 10 5 252
81 9 5 126
82 8 5 56
83 7 5 21
84 6 5 6
85 5 5 1

Innanzitutto la generazione più lunga sarebbe stata quella per il "numero iniziale" 1: facendo due calcoli si può notare come si tratti comunque di meno del 7% del totale delle combinazioni, quindi una riduzione considerevole.
Inoltre, per gli ultimi "numero iniziale" (prossimi all'85) abbiamo un numero di combinazioni molto basso (fino al numero 85, caso che ovviamente genera un'unica combinazione) e questo è ideale per verificare la corretta esecuzione della procedura.

Qui sotto riporto la routine modificata che genera le combinazioni; da notare che questa scrive direttamente su disco senza passare per strutture intermedie e che ad ogni passaggio verifica se l'utente vuole interrompere la procedura (gstopthread).

void combina(int starting, int k, int* out, int out_pos)
{
int i;
for (i = starting; i <= (90 - k + 1); i++)
{
out[out_pos] = i;
if (k > 1)
{
combina(i + 1, (k - 1), out, (out_pos + 1));
}
else
{
gcnt++;
fprintf(gfpout, "%i;%i;%i;%i;%i;%i\n", out[0], out[1], out[2], out[3], out[4], out[5]);
}

if (gstopthread)
break;
}
}

 

INTERFACCIA GRAFICA

Ho sviluppato l'interfaccia grafica utilizzando le API Win32.
In pratica alll'utente chiedo, con una combobox, di specificare il "primo numero" oppure tutte le combinazioni e, con una checkbox, gli permetto di selezionare anche tutti i successivi numeri iniziali; dopo aver scelto il nome del file in cui scrivere è sufficiente premere Esegui per iniziare l'elaborazione.
L'interfaccia è naturalmente molto spartana; eventualmente in futuro, se a qualcuno interessasse, la renderò più "carina"! 

genena

 

TEMPI E RISULTATI

Su un PC di media potenza la generazione di tutte le combinazioni ha richiesto una decina di minuti mentre il file risultante ha una dimensione di quasi 11 Gb (comprimendolo si arriva a "solo" 1 Gb): effettivamente avrei avuto qualche problema a trasferire tutti questi dati!!!

 

CONCLUSIONI

Confesso di essere rimasto sorpreso dei buoni risultati in termini di tempo di esecuzione, anche sulla generazione di tutte le combinazioni; immaginavo che, oltre alla semplice generazione delle combinazioni, la creazione di un file così corposo mi avrebbe rallentato parecchio.
Rimane un problema: i file di testo creati non possono essere aperti con tutti gli editor, a causa del numero elevato di righe; lo stesso Excel ha un limite di 1 milione di righe... ad ogni modo a Vincenzo andava bene così!

Ah, dimenticavo, il programma (completo di sorgenti) lo trovate nell'area download di questo stesso sito!

Buon divertimento!!!