Ricerca non euristica di lunghette vergini per minimo fissato

Ciao Forum,
apro questo thread per discutere su un algoritmo per la ricerca di lunghette, ovvero combinazioni di numeri di lunghezza fissata (ad esempio nove numeri, ovvero novine) che abbiano una determinata caratteristica: proveremo a cercare le lunghette che non hanno mai fatto 3 punti ( e naturalmente neanche più di tre punti) in un certo intervallo di combinazioni. Inizialmente prenderemo alcune estrazioni di sei numeri del superenalotto. Ma vogliamo che l'algoritmo sia alternativo al procedimento tramite forza bruta (che esamina tutte, una per una dalla prima all’ultima, sequenzialmente tutte le possibili soluzioni al fine di individuare quella o quelle cercate).
Ricordo che per seguire meglio questo discorso è bene rileggere quella dozzina circa, di post passati nei quali abbiamo avuto modo di fare le prime valutazioni e i primi esperimenti.
Abbiamo iniziato a parlare di questo argomento replicando a un intervento del prof Di Guida su una discussione avviata da sasalino.
I post sono visionabili dal punto a cui si accede dal seguente link in poi sino almeno alla data di oggi, in ordine cronologico verso il basso:
#entry459776457

Detto questo,
devo ammettere che attualmente non so se la mia idea è buona.
Ma sono certo che mi pare ragionevole confrontarmi con altri esperti. Ho fatto solo un paio di prove simulando le mosse di un software che deve seguire delle istruzioni precise e formali senza curarsi di quello che sta cercando. Quindi dopo poco mi sono stancato senza produrre niente se non alcuni appunti da cui poter riprendere il filo il giorno seguente.
Potrebbe però essere un metodo valido e dare origine a uno strumento utile anche in futuro e quindi pensavo che magari, se servirà scambiare qualche battuta insieme, si potrebbe dedicare questo primo post della discussione all'introduzione del materiale necessario in partenza in modo che, rimanendo in alto a questa pagina, sia facile da reperire in un secondo momento.
Quindi posto in allegato:
- Il file di testo con le 2093 estrazioni del superenalotto (che vanno dal 02 luglio 2009 la prima riga in alto, sino al 24 dicembre 2022 l’ultima riga in fondo al file), in modo da fare riferimento a queste evitando di incartarci con archivi differenti e discordanti.
- Poi serve il file Excel che ho preparato per fare le prove. Contiene le estrazioni di cui sopra, ma in formato di matrice booleana. Nella prima riga in alto si può leggere la prima estrazione (12 13 38 46 47 72) la quale invece che essere scritta coi numeri naturali è espressa sotto forma di una sequenza di 90 bit dove 1 significa che il corrispondente numero di quella colonna è uscito in quella estrazione; mentre 0 oppure cella vuota significa che il numero non è presente.
Mi pare si chiami, oltre che genericamente “boolean matrix” o “bit matrix”, più tecnicamente “adjacency matrix”, ma mi riservo di appurare la corrispondenza di quest'ultimo termine successivamente.
Infine, siccome il file Excel è lungo la bellezza di 32 pagine, posto qui sotto un’elaborazione grafica in cui si vedono solo le estremità della suddetta matrice booleana, in modo che si possa più facilmente esaminare in generale come è strutturato tale file.. Al centro la matrice è spaccata in quattro e tre puntini stanno a indicare la continuità dell’elaborato

Si noti che le prime due righe, in assoluto in alto, contengono:
la prima in blu, la somma delle volte in cui quel numero è uscito nelle2093 estrazioni (che è anche detta “frequenza” di quel numero nelle 2093 estrazioni
in esame) in pratica non è altro che la somma dei segni 1 in verticale.
La seconda in verde, facilita la lettura riportando il numero stesso da 1 a 90 cui quella colonna si riferisce.
La prima colonna, in arancio, invece, come è facile intuire riporta il numero del relativo concorso che ho numerato da 1 a 2093 per semplicità.

E’ più facile a farsi che a dirsi!

Per adesso però dobbiamo fare una pausa e vederci per la descrizione delle mosse da fare secondo l’algoritmo col prossimo post.
Grazie per la lettura.

Edited by stef72 - 29/12/2022, 13:38

A questo punto vi chiederete perché ragionare in questa maniera...Che non si capisce niente, non ci sono nemmeno le date dei concorsi e per sapere che numero è uscito bisogna pure usare il mouse per salire su e vedere in quale colonna è stato messo il segno 1 che abbiamo davanti.

Intanto secondo me occorre stabilire dei parametri che magari poi diventeranno variabili, ma che adesso poniamo essere fissi per la nostra ricerca. Quindi stabiliamo che vogliamo cercare una lunghetta di 9 numeri, ovvero una novina, che abbia la caratteristica di non aver totalizzato mai, in nessuna delle estrazioni …3 punti o più di tre punti.

Cioè sia dato che per la nostra ricerca stiamo cercando una novina vergine per tre punti sulle 2093 estrazioni.

A questo punto è il momento di iniziare a applicare un algoritmo.

La ricerca verrà effettuata un numero per volta (della novina da costruire).
Per descrivere il funzionamento non inizierò dal numero uno, per poi provare a aggiungere il due, poi il tre, e magari fare un passo indietro…e così via, come poi probabilmente farà il programma nel suo percorso prestabilito, ma, per evidenziare i punti cruciali, prenderò un momento dell’elaborazione a noi conveniente per capire proprio il fulcro del procedimento.
Pensiamo di aver provato già alcuni passi e di aver quindi escluso le prime combinazioni secondo un certo ordine e che quindi sia arrivato il momento di provare i prossimi numeri inziali che sono il 2, assieme al 31

Io ho scelto di evidenziare con sfondo verde l’intera colonna corrispondente al numero selezionato (per selezionare l’intera colonna basta cliccare in cima alla colonna per evidenziarla tutta e poi cambiare i colore)
Quindi abbiamo selezionato i primi due numeri di quella che sarà la novina candidata e che speriamo soddisfi il criterio di non aver totalizzato tre punti.
Ora cosa succede…

(Forse ho dimenticato di attivare la funzione di filtro in Excel sul foglio che ho allegato, ma se serve chiedete pure come fare o se necessario cambio l’allegato)

Attiviamo il filtro in modo da farci mostrare solo le righe della matrice che hanno 1 in quella colonna (l’operazione del filtro in figura deve essere applicata contemporaneamente sial per il numero 2 sia per il 31)
Vedremo a video la seguente situazione:

Potrebbe sembrare insignificante, ma è proprio qui che otteniamo l’informazione che facilita l’intero il lavoro:
In pratica così riusciamo a mettere la macchina in grado di escludere a priori alcuni passi e permettere di contrassegnare alcune scelte come mosse proibite, invece di effettuarle indiscriminatamente tutte quelle possibili.

Perché se il computer fosse libero di perdere tempo a scegliere di provare come terzo numero della novina, il numero 4, sarebbe arrivato a comporre (2 4 31) per fare la novina, ma allora l’estrazione nr 980 avrebbe totalizzato 3 punti (facendo la somma degli 1 in orizzontale) e questo abbiamo stabilito essere uno dei risultati che deve essere evitato.

Certamente qualcuno di voi avrà già progredito nel discorso, ma ancora non è chiaro perché questo metodo, secondo me, porterebbe dei vantaggi enormi in termini di tempo di elaborazione anche in presenza di input molto più grandi (penso si possa chiedere più dei nove numeri come la novina del nostro esempio, ma anche che non totalizzi non tre punti, ma quattro, cinque ecc, quale punteggio da non realizzare).

Edited by stef72 - 29/12/2022, 11:43

Sto cercando di capire cosa intendi fare. Mi sembra sia un metodo totalmente differente da quelli provati sino a ora.
Ricapitolando quanto hai detto, prendiamo il 90,9,5,9=40290 e lo utilizziamo come se fosse un 90,9,6,16=40290
Ma non capisco perchè entrano in ballo le 16ine
Se vuoi però posso darti il 90,9,6,16 in modo, almeno, che possa utilizzare direttamente questo senza dover ricorrere a succedanei:

allego 90,09,06,16=35.478

Ok, ora cerco anche di concludere la descrizione
così eventualmente si potrà passare a qualche prova e qualche osservazione per migliorare ulteriormente il modo di procedere.

Prendiamo come esempio questi primi numeri scelti da una fase dell’algoritmo:
2 31 48 49 50 58 59 ,
in questa immagine si vede come questi 7 numeri scelti impongano solo altri due numeri come possibili componenti per arrivare a completare la novina. Sono le uniche due colonne rimaste in bianco...
(clicca sulla miniatura per ingrandire) (che poi ho usato per questo esempio, i numeri di una delle 4 novine del prof Di Guida che quindi sappiamo già essere una soluzioni valida)
I numeri che il computer ha già scelto in questo ciclo e dovrà provare ad abbinare ad altri due finire di per comporre la novina, sono le sette colonne in verde.
In arancione invece sono contrassegnati tutti i numeri che ciascuna delle sette scelte precedenti ha reso non utilizzabili. La scelta di un solo numero applica il contrassegno (in arancione) di diverse colonne, direi anche una decina. Perciò in certi casi, in poche mosse ci si rende subito conto di non poter proseguire e si può saltare al passo successivo.

Un altro algoritmo invece sarebbe andato avanti alla cieca sino a completare la novina per poi effettuare la verifica e vedere poi che totalizza magari, che so…, 8 punti 😊

Col foglio Excel dell’allegato al primo post potete provare manualmente come ho fatto io a iniziare a inventare i primi numeri di una vostra novina qualsiasi e, avendo cura di segnare in arancione tutte quelle colonne che, dopo aver regolato i due filtri, presentano un 1 su sfondo bianco . Vi renderete conto immediatamente se state seguendo una strada sbagliata.



Una cosa importante che stavo per tralasciare è che ogni volta che si aggiunge un numero, dopo aver contrassegnato la scelta in verde, si devono applicare i filtri a tutte le possibili coppie del nuovo numero appena aggiunto, a uno a uno per fare coppia appunto, a turno, con gli altri già in verde.

Cioè, per esempio, se sto inserendo il quarto numero della novina,
diciamo che siamo arrivati a provare 2 31 48 e voglio aggiungere il 49
devo subito provare se questo genera tre punti, prima mettendo il filtro Excel sulla prima colonna in verde con la nuova colonna in verde del quarto numero, poi filtro la seconda colonna verde con la quarta, infine la terza sempre con la quarta. Ogni volta che applico i filtri a una coppia di colonne, osservo gli 1 che sono nelle colonne ancora in bianco e queste diverranno arancioni.

In sostanza, per ogni n-esimo numero che aggiungo, devo fare (n-1) confronti applicando i filtri due a due sulle colonne verdi


A intuito mi pare che la complessità sia enormemente inferiore a quella della costruzione di tutte possibili le novine con un altro algoritmo.
La parte di codice che credo mi impegnerebbe maggiormente è forse la gestione del backup dell’ultimo passo corretto, ovvero mantenere traccia del punto in cui siamo arrivati per poter poi ripristinare i passi effettuati quando ci si accorge che il candidato non va bene; E poter poi seguire la strada successiva. Sino a esaurire tutte le possibilità…tra quelle ammissibili.
Cioè, nel mio post precedente abbiamo visto come dopo aver scelto il 2 e il 31 non possa essere scelto il 4, allora si procederebbe provare un altro numero candidato come terza scelta (scegliendo tra quelli rimasti ancora in bianco che non sono cioè contrassegnati in arancione). Se anche questo non può andare bene si passa a un altro numero più avanti e poi un altro ancora, e così sino al limite dei 90 numeri. Dopodiché avremmo stabilito che il 2 e il 31 non vanno bene con nessun numero. Quindi si dovrà fare un passo indietro e mutare uno dei primi due numeri scelti. Mantenendo cioè il 2 e procedendo col candidato successivo al 31. Per poi riiniziare la prova del terzo candidato, non più assieme a 2 e 31, ma per esempio assieme al 2 e al 32.

Mi pare che non resti che provare

E' vero, grazie! E' una svista anche se non altera il contenuto dei post successivi.
Ho corretto comprendendo nella somma anche l'ultima riga e ho approfittato per inserire nel nuovo foglio anche i filtri (le freccette nere verso il basso) già pronti per poter essere manovrati.

Io non so se userei la ricorsione. Sarebbe anche più elegante, ma se mi dovessi anche avventurare con la ricorsione mi perderei per strada. Penso invece che inizierei con un grande ciclo While che si arresta quando i numeri scelti sono 9 oppure quando non ci sono più alternative da provare. Con un indicatore che permetta di seguire il progresso dei calcoli.
Si i calcoli son tanti, ma da quello che ho visto provando a mano mi pare che si riducano tantissimo. proprio perché arrivato a certi abbinamenti di numeri salta per intero grandi rami dell'albero delle possibili novine.
Se osservi questa immagine (che ho già usato nel post precedente) si vede bene che quando inserisci il 59 come settimo numero rimane una sola scelta possibile, cioè quella aggiungere il 70 e il 73. Mentre un algoritmo euristico si metterebbe a provare tutte le coppie di numeri, compresi quelli in arancione (che noi sappiamo che originerebbero un terno) e sono tante. Se non sbaglio C(90-7 ; 2)=3403. Questo avviene solo in questo momento dell'esecuzione, ma questi 'tagli' avvengono ripetutamente mentre ci si avvicina alla fine della ricerca.
Però no, non ho fatto nessun codice. Mi servirebbe una giornata di quelle che non hai niente da fare.

Cosa ti preoccupa degli ambi che non sono mai usciti? Non vedo il problema.

Non voglio partire dagli ambi.

Inizia così
1 2 3
, scegliendo il numero 1, poi siccome non ci sono celle in arancione, sceglie il numero 2, così anche per il 3 va avanti liscio,
poi il quarto numero (e i successivi) saranno una scelta (molto ridotta) tra i numeri in bianco (7 8 12 13 14 15 16 17 18 20 22 24 25 26 28 29 31 32 36 37 40 43 44 45 46 47 48 50 51 52 53 58 59 63 65 66 68 71 72 77 80 81 86 87 89) della seguente immagine:

(clicca sulla miniatura per ingrandire)

Se un software euristico, che genera a ruota tutte le possibili combinazioni, per arrivare alla prima combinazione che dopo il 3 ha il numero 7 (1 2 3 7 8 9 10 11 12) deve prima esaminare 98.499.836 novine (indice lessicografico di questa) le quali daranno tutte almeno 3 punti (dalla 1 2 3 4 5 6 7 8 9 alla 1 2 3 7 8 9 10 11 12) quindi non ci interessano.
Noi invece, questo lo vediamo prima di metterci a costruire le novine e di verificarle! Lo vediamo perché abbiamo davanti i numeri in arancione e sappiamo che fanno male. Non si toccano! Pucci, cacca! Come ci diceva la mamma!
Come quinto numero sceglierà il numero 8… (i numeri in memoria saranno 1 2 3 7 8)

Più significativo è forse il passo successivo:
L’algoritmo euristico di forza bruta, continua a costruire le novine e le esamina ancora tutte, come se avesse i paraocchi, da quella successiva con la sequenza già selezionata: 1 2 3 7 8 9 10 11 12 di indice =98.499.836 a quella che, nell'ordine lessicografico ha il 24 come sesto numero; Ovvero questa: 1 2 3 7 8 24 25 26 27 di indice=99.482.416). perciò ne costruisce e esamina…inutilmente… 99.482.416- 98.499.836= 982.580
mentre con questo nuovo algoritmo esse vengono saltate (sempre grazie ai numeri in arancio, che noi guardiamo e passiamo, passiamo oltre).

Per concludere, è interessante che dopo questa sequenza di prova: dopo questa sequenza di prova: 1 2 3 7 8, la situazione dei colori farebbe tentare come prossimo il 24, ma contrassegnando in arancio le colonne coinvolte da questo, non rimerrebbe nessun numero libero in bianco da poter sceglieree così non si arriverebbe a completare la novina (ci si bloccherebbe a sei numeri 1 2 3 7 8 24, senza possibilità di procedere).
Quindi si dovrà tornare indietro dell’ultima mossa (il 24) e ripetere la scelta del sesto numero (che nel nostro caso sarà il 36)… (clicca sulla miniature per ingrandire)

Potrei anche sbagliarmi. Aver omesso di considerare qualche lato del lavoro che il PC dovrà fare e che si traduce in un rallentamento, perciò, alla fine dovremmo aspettare ore e ore sia col primo sia col questo di algoritmo.
Ma sono ancora convinto di non sbagliare.
Penso anche che qualcuno che ha letto le dritte (non necessariamente un utente affezionato del Forum) abbia già messo qualcosa in pentola e magari ha già quella preziosa informazione che ci incoraggerebbe oppure ci farebbe demordere dall’intento di mettersi lì a buttare una giornata di lavoro per cercare spiegare a una fredda macchina cosa vogliono dire le figure descritte nei post sopra.

Edited by stef72 - 1/1/2023, 10:09

Esatto! Mi rendo conto di aver sbagliato a mettere i colori (sto lavorando con un monitor da 15" che sembra un orologio da polso! Lo so è vergognoso)
Infatti la corretta esecuzione dell'algoritmo il 4 lo esclude contrassegnandolo in arancione quando applichi i filtri.
Da una parte però mi fa piacere che il discorso sia chiaro. Altrimenti non avresti individuato l'errore, almeno credo

Lasciami modificare i conteggi e cambiare le relative immagini al mio post precedente in modo che si possa rileggere. Sempre però col beneficio del dubbio, perchè sono un po' stanco e sta diventanto tedioso dover fotografare qualsiasi microoperazione che devo fare a mano.

Ora il post sopra è tutto corretto.