PROBLEMA [C] Estrazione tipo superenalotto

[BAT]

bastano solo 6 scambi per ottenere una sestina perfettamente casuale.
Se poi ritieni comunque che quello che dico sia sbagliato, allora spiegami e dimostrami il perché

non è sbagliato il ragionamento ma il presupposto:
il randomizzatore integrato in C (ma non solo quello del C) non genera numeri sufficientemnete casuali o, in altri termini, non genera sequenze casuali di probabilità uniforme. Le implementazioni dei rand(), sono poco sofisticate per questioni di efficienza, ed generano se quenze "troppo poco" casuali, anche se ad occhio non si vede.

Per un esercizio "scolastico" il metodo proposto va bene, ma ci dobbiamo chiedere se si possa far meglio. Aumentare di molto il numero di scambi (come avevo proposto) sposta solo un po' più in là i termini della questione.
Devo aprire un off-topic
A meno di non ricorrere a librerie specializzatte esterne, con il solo randomizzatore incorporato, per mitigare il problema della "pseudocasualità troppo poco casuale" è cercare di introdurre elementi che possano amentare l'incertezza del risultato (il prossimo numero della sequenza), per esempio:

• dare un seme (un numero) con l'istruzione srand(time(0));o simili --> imposta un seme abbastanza casuale e non prevedibile (perché basato sul conteggio di secondi trascorsi da una certa data) che sarà usato dal randomizzatore per generare le sequenze. Le sequenze saranno indici dell'array (da dividere modulo 90 per essere certi di ricadere nel range giusto)
• una seconda domanda potrebbe essere "quanti scambi faccio? (min X -max Y)", contando sul fatto che (si spera) il numero che viene in mente all'utente sia diverso di volta in volta (il che può non essere vero ed in tal caso ci si affida al solo seme del punto precedente), o altrimenti si genera un nuovo intero casuale compreso in un certo range per "casualizzare" anche il numero di scambi. A occhio il minimo per me è 45, per dare una chance di scambiare almeno una volta ciascun elemento (anche se questo non toglie che lo stesso numero potrebbe essere scambiato più volte ed altri invece mai)
• con il seme introdotto al primo punto si può essere ragionevolmente certi che le sequenze di indici da scambiare saranno diverse ogni volta che si lancia il programma. Con il secondo punto si dovrebbe "mischiare" meglio l'array

 

[M1n021]

@BAT scusami, ma mi sembra che tu stia spostando l'attenzione su questioni (peraltro con argomenti non molto rigorosi) che nulla c'entrano con quello di cui stavamo discutendo in precedenza.

Per un esercizio "scolastico" il metodo proposto va bene, ma ci dobbiamo chiedere se si possa far meglio.

A di la verità, nei precedenti messaggi mi sembravi molto più drastico nel bocciare il procedimento da me proposto.

In ogni caso ci tengo a ribadire che una cosa è l'algoritmo risolutivo da adottare (che è l'argomento della discussione), un'altra è tutta la questione (poco pertinente, per quanto interessante) sui generatori di numeri pseudocasuali. E relativamente all'algoritmo risolutivo, ritengo che i punti fondamentali siano: l'utilizzo di un approccio deterministico, l'efficienza e assicurare una distribuzione uniforme delle probabilità; tutte cose che la soluzione da me proposta sembra soddisfare.
Inoltre, sempre restando nell'ottica dello stesso algoritmo, non vedo come il mescolare più volte l'array possa aggiungere ulteriore aleatorietà rispetto alla sequenza ottenuta con un singolo "mescolamento".

una seconda domanda potrebbe essere "quanti scambi faccio? [...] A occhio il minimo per me è 45, per dare una chance di scambiare almeno una volta ciascun elemento (anche se questo non toglie che lo stesso numero potrebbe essere scambiato più volte ed altri invece mai)

Queste parole mi convincono sempre di più del fatto che tu non abbia capito fino in fondo come funzioni la funzione mischia_array() postata in precedenza. Quello da te delineato mi sembra infatti un approccio non deterministico basato sullo scambio di generiche coppie di elementi casuali dell'array.

 

[Andretti60]

?Avete tutti fondamentalmente ragione.

L’algoritmo più comunemente usato per generare una lista di elementi ordinati (Fisher-Yates e ulteriori ottimizzazioni) funziona, quindi per ordinare N elementi bastano quindi N iterazioni (è dimostrato, facilmente). Purtroppo funziona solo in presenza di un buon PRNG (generatore di numeri pseudo casuali), e qui c’è la grande battaglia, quale PRNG sia migliore degli altri. Non solo, ma quanto veloce sia, perché un conto è mischiare un mazzo di 52 carte, un conto è effettuare una simulazione di un processo stocastico mediante il metodo di Monte Carlo (tanto per fare un esempio che conosco bene) che richiede milioni e milioni di operazioni (può durare giorni per completare a seconda del caso). Esistono generatori di numeri casuali Hardware, che utilizzano un sensore che legge una sorgente di rumore prodotta da un sistema fisico (in genere un processo quantistico), ma hanno il problema che sono estremamente lenti, possono produrre pochi numeri al secondo, sono in genere usati in crittografia per generare i “semi” usati per inizializzare una sequenza PRNG.
E c’è un ulteriore problema: il bias prodotto dalla normalizzazione del numero casuale nell’intervallo desiderato. Per esempio il metodo più comune è la funzione modulo, che va bene solo se il nostro intervallo è molto minore dell’intervallo naturale dei numeri prodotti dal PRNG.
La buona notizia è che, in pratica, basta conoscere le limitazioni e applicare il giusto algoritmo al problema specifico, e i risultati che si ottengono sono sempre validi. Per esempio, per mischiare un mazzo di carte la funzione rand() nativa in quasi tutti i linguaggi di programmazione va più che bene, anche usando poi la funzione modulo.

@BAT sarai interessato a sapere che bastano quattro mischiate (se fatte bene) per un mazzo di carte, e più di sette non cambiano nulla, è stato dimostrato Matematicamente.

 

[BAT]

Purtroppo funziona solo in presenza di un buon PRNG (generatore di numeri pseudo casuali), e qui c’è la grande battaglia, quale PRNG sia migliore degli altri.

? era questo che cercavo di far capire, purtroppo nella fretta di scrivere a volte non mi riesce tanto bene

@BAT sarai interessato a sapere che bastano quattro mischiate (se fatte bene) per un mazzo di carte, e più di sette non cambiano nulla, è stato dimostrato Matematicamente.

sì, sono interessato e sì lo sapevo, comunue grazie lo stesso ? lo rileggerò con piacere
[EDIT] articolo non pubblico, ma non fa niente se ne trovano molti altri

A di la verità, nei precedenti messaggi mi sembravi molto più drastico nel bocciare il procedimento da me proposto.

non ho bocciato il metodo, solo il numero di scambi eccessivamente limitato

Quello da te delineato mi sembra infatti un approccio non deterministico basato sullo scambio di generiche coppie di elementi casuali dell'array

se fosse non deterministico per davvero ne sarei felice (parlo degli scambi di coppie di elementi), purtoppo non lo è, essendo legato al randomizzaotre pseudocasuale, è un finto nondeterminismo ?

assicurare una distribuzione uniforme delle probabilità; tutte cose che la soluzione da me proposta sembra soddisfare

sfortunatamente no, ma forse non riesco a farmi capire: un generatore random (standard) non te la può garantire
non prenderla come un'accusa è solo un'osservazione: se il randomizzatore fosse perfetto la via era quella, ma non lo è
inoltre per mischiare "bene" un array da n elementi vanno fatte n-1 generazioni di numeri (pseudo)casuali, qui l'array è da 90 elementi, per cui ne vanno fatte 89

non vedo come il mescolare più volte l'array possa aggiungere ulteriore aleatorietà rispetto alla sequenza ottenuta con un singolo "mescolamento"

una sestina vincente è una combinazione di 6 elementi presi da 90 (combinazione)
la descrizione in pseudocodice dell'algoritmo (esegui 6 scambi che coinvolgono i primi 6 elementi) di fatto diminuisce drasticamente che si verifichi l'uscita di 1,2,3,4,5,6 (non necessariamente in questo ordine) rispetto a tutte le altre combinazioni di 6 elementi;
in altri termini usando un randomizzatore standard, con soli 6 scambi la sestina 1,2,3,4,5,6 (eventualmente non in questo ordine) non ha la stessa probabilità di altre sestine di trovarsi nelle prime 6 posizioni dell'array, la probabilità sale solo se aumenti drasticamente il numero di scambi .

Nota bene: ho ripetuto più volte "usando il randomizzatore standard non va bene [...il numero limitato di scambi]" è quello il pomo della discordia, non l'algoritmo di scelta dei primi 6 elementi su cui concordiamo tutti

 

[M1n021]

?Avete tutti fondamentalmente ragione.

L’algoritmo più comunemente usato per generare una lista di elementi ordinati (Fisher-Yates e ulteriori ottimizzazioni) funziona, quindi per ordinare N elementi bastano quindi N iterazioni (è dimostrato, facilmente). Purtroppo funziona solo in presenza di un buon PRNG (generatore di numeri pseudo casuali), e qui c’è la grande battaglia, quale PRNG sia migliore degli altri.

Certo, ma inizialmente la discussione era incentrata sull'algoritmo risolutivo e non sui generatori di numeri pseudocasuali, anche perché con queste premesse dovremmo finire per intraprendere interminabili diatribe scientifico/filosofiche sui PRNG ogni qual volta in un thread si faccia riferimento alla funzione rand(), o no?!

@BAT sinceramente non so quanto sia utile replicare, anche perché finirei per ripetere sempre le stesse cose... ad ogni modo provo a puntualizzare giusto un paio di cose:

se fosse non deterministico ne sarei felice (parlo degli scambi di coppia), purtoppo non lo è, essendo legato al randomizzaotre pseudocasuale

Magari non mi sono espresso in maniera rigorosa, ma con approccio deterministico intendevo dire che, al netto della generazione di numeri pseudocasuali, l'algoritmo da me proposto richiede sempre lo stesso numero di passaggi predeterminati, a differenza di quello che accade per esempio nell'approccio consigliato all'OP di verificare volta per volta se il numero casuale generato non fosse già stato "estratto" in precedenza.

è questo che non va, ma forse non riesco a farmi capire: un generatore random (standard) non te la può garantire

Come sopra, non si sta parlando di efficienza del PRNG, ma del fatto che un algoritmo produca (come nel caso del Fisher-Yates) o meno (come l'algoritmo descritto dall'immagine in questo post) una distribuzione di probabilità uniforme.

la descrizione in pseudocodice dell'algoritmo (esegui 6 scambi che coinvolgono i primi 6 elementi) di fatto diminuisce drasticamente che si verifichi l'uscita di 1,2,3,4,5,6 (non necessariamente in questo ordine) rispetto a tutte le altre combinazioni di 6 elementi;
in altri termini usando un randomizzatore standard, con soli 6 scambi la sestina 1,2,3,4,5,6 (eventualmente non in questo ordine) non ha la stessa probabilità di altre sestine di trovarsi nelle prime 6 posizioni dell'array, la probabilità sale solo se aumenti drasticamente il numero di scambi .

Anche qui, ammessi pure tutti i limiti che si vogliono attribuire ad un determinato PRNG, davvero non capisco su quali basi poggino queste tue sentenze così categoriche!

 

[BAT]

davvero non capisco su quali basi poggino queste tue sentenze così categoriche

si basano sullo studio della teoria fatto all'università in uno dei corsi di algoritmi e strutture dati che avevo nel piano di studi...
cosa caratterizza un buon algorimo? 2 cose imprescindibili:

1. deve essere corretto --> ossia deve generare un risultato giusto
2. deve essere completo --> significa che deve contemplare tutti i casi possibili

Il tuo algoritmo è corretto perchè produce un risultato giusto,
tuttavia non è completo perché, a prescindere dalla bontà del randomizzatore non tiene conto di tutti i casi possibili.
Perché? perché non mischia sufficientemente "bene"
A parte il randomizzatore che può essere più o meno buono (o cattivo) è ampiamente dimostrato che per mischiare "bene" un array di N elementi occorre generare N-1 numeri pseudocasuali (ed applicare i passi dell'algoritmo);
i passi delll'algoritmo li trovi in uno dei 3 testi (all'epoca erano 3, ora sono di più) di Donald Knuth, "The Art of Computer Programming", non ricordo esattamente quale perché sono passati più di 20 anni da quando lo lessi ? e ho perso pure le fotocopie che mi feci, però mi ricordo che il capitolo si intitolava "Shuffling" (=mischiare). Nell'algoritmo uno dei passi era "generare un numero casuale" (il che implica avere un buon randomizzatore e questo non è quasi mai il caso anche se nei problemi semplici ci dobbiamo accontentare di quello integrato nel linguagio).
Per "accontentarci" senza ignorare la teoria, devi solo fare 89 generazioni di numeri pseudocasuali invece di 6 ed applicare i passi descritti in quell'algoritmo, tutto qui (se non ricordo male si tratta solo di fare degli scambi in modo adeguato).

[EDIT]
per NON applicare l'algoritmo di Knuth (o l'altro citato da Andretti) e fare solo 6 estrazioni senza mischiare necessariamente tutto il mazzo, sarebbe indispensabile avere un randomizzatore perfetto: in quel caso è ovvio che estrai un indice, prendi l'elemento e lo metti in prima posizione (scambiandolo), poi estrai un nuovo indice, prendi l'elemento e lo metti in seconda posizione,.. fino ad averne 6. Ma serve il randomizzatore perfetto (che non abbiamo purtroppo).

 

[M1n021]

si basano sullo studio della teoria fatto all'università in uno dei corsi di algoritmi e strutture dati che avevo nel piano di studi...
[...]
i passi delll'algoritmo li trovi in uno dei 3 testi (all'epoca erano 3, ora sono di più) di Donald Knuth, "The Art of Computer Programming", non ricordo esattamente quale perché sono passati più di 20 anni da quando lo lessi ? e ho perso pure le fotocopie che mi feci, però mi ricordo che il capitolo si intitolava "Shuffling" (=mischiare).

Premetto che non sono del settore, e infatti utilizzo la programmazione (fondamentalmente C e C++) come puro esercizio di logica. Quindi non ho assolutamente la pretesa essere infallibile, anzi ?, ma proprio per questo trovo molto costruttivo un sano dibattito nel merito delle questioni, tutto qui!
Fatte le dovute premesse, semplicemente non capisco come fai ad affermare che:

la descrizione in pseudocodice dell'algoritmo (esegui 6 scambi che coinvolgono i primi 6 elementi) di fatto diminuisce drasticamente che si verifichi l'uscita di 1,2,3,4,5,6 (non necessariamente in questo ordine) rispetto a tutte le altre combinazioni di 6 elementi;

Perché la combinazione 1,2,3,4,5,6 dovrebbe essere meno probabile delle altre?

A parte il randomizzatore che può essere più o meno buono (o cattivo) è ampiamente dimostrato che per mischiare "bene" un array di N elementi occorre generare N-1 numeri pseudocasuali (ed applicare i passi dell'algoritmo);
[...]
Per "accontentarci" senza ignorare la teoria, devi solo fare 89 generazioni di numeri pseudocasuali invece di 6 ed applicare i passi descritti in quell'algoritmo, tutto qui (se non ricordo male si tratta solo di fare degli scambi in modo adeguato).

Il punto è che se guardi bene la funzione mischia_array() (che da quanto ho capito sarebbe una sorta di Fisher-Yates), ti renderai conto che all'i-esima iterazione del ciclo puoi andare a modificare solo gli elementi che si trovano a destra dell'elemento dell'array di indice i, quindi dopo i primi 6 scambi, i primi 6 elementi della sequenza "mischiata" sono ormai definiti, in quanto non possono essere ulteriormente modificati dalle restanti 83 iterazioni necessarie per completare il mescolamento dell'array.

 

[BAT]

Premetto che non sono del settore, e infatti utilizzo la programmazione (fondamentalmente C e C++) come puro esercizio di logica. Quindi non ho assolutamente la pretesa essere infallibile, anzi ?, ma proprio per questo trovo molto costruttivo un sano dibattito nel merito delle questioni, tutto qui!

? è corretto: non vedo perché ci si dovrebbe accontentare dell'ipse-dixit, non fosse altro per il fatto che "ipse" può sbagliare ? (magari in buona fede, ma si sa che la strada dell'inferno è lastricata di buone intenzioni ed io non sono certo immune)

Perché la combinazione 1,2,3,4,5,6 dovrebbe essere meno probabile delle altre?

perché secondo me il randomizzatore standard toglierà sistematicamente di mezzo tutti o in parte questi numeri.
L'unico modo per farli rimanere tutti e 6 è generare solo numeri compresi tra 0 e 5 per 6 volte di seguito avendo come limite massimo da generare il numero 89 (d'altra parte se anche una sola volta vai fuori range 0-5 sposti nelle prime 6 posizioni un numero che non tocchi più perché dopo agisci solo alla sua destra, e questo annulla la possibilità della sestina);
quindi la prima volta deve generare un intero tra 0-5, la seconda tra 1-5, la terza tra 2-5, la quarta tra 3-5, la quinta tra 4-5, e l'ultima per forza 5) --> con un generatore pseudocasuale perfetto è possibile, ma con uno pseudocasuale standard (ad aritmetica modulare e congruenze lineari) temo che non lo sia e ti spiego perché:

1. per generare un numero compreso tra 0 e 5 con un limite massimo di 89 ci sono 6 possibilità su 90, cioè 6/90 --> 1/15
2. tra 1-5 sono 5 su 89, cioè 5/89
3. tra 2-5 sono 4 su 88 cioè 4/88 --> 1/22
4. tra 3-5 sono 3 su 87 cioè 3/87 --> 1/29
5. tra 4-5 sono 2 su 86 cioè 2/86 --> 1/43
6. tra 5-5 è 1 su 85 --> 1/85

la probailità dell'evento, con 2 rapidi conti (basta moltiplicare le frazioni precedenti) è 1 su 622.614.630 --> guarda caso questo è esattamente il numero di combinazioni di 6 elementi scelti tra 90 ossia il coefficiente binomiale 90 su 6 = 90!/(6!*84!), ossia la probabilità di fare 6 al Superenalotto! Il che significa che per avere la sestina 1,2,3,4,5,6 allora il generatore pseudocasuale standard (imperfetto per definizione di pseudocasualità) si comporterebbe esattamente come un generatore perfetto! ? se sei un appassionato di logica dovrebbe essere sufficiente a convincerti

è che se guardi bene la funzione mischia_array() (che da quanto ho capito sarebbe una sorta di Fisher-Yates), ti renderai conto che all'i-esima iterazione del ciclo puoi andare a modificare solo gli elementi che si trovano a destra dell'elemento

verissimo, ma il problema è il punto precedente: le sestine devono essere equiprobabili
è il motivo per cui innalzando di molto il numero di scambi senza conservare posizioni tento disperatamente di simulare una casualità più simile a quella reale; è un metodo un po' "balordo" ed inefficiente, però funziona.

P.S.
se non mi vedi fino a domani pomeriggio non è che non voglio risponderti, solo che non ci sono

 

[M1n021]

@BAT ho letto con attenzione quello che hai scritto: sui calcoli nulla da eccepire, ma, mi duole ammetterlo, la conclusione che ne trai

Il che significa che per avere la sestina 1,2,3,4,5,6 allora il generatore pseudocasuale standard (imperfetto per definizione di pseudocasualità) si comporterebbe esattamente come un generatore perfetto!

non mi convince più di tanto! ?

P.S.
se non mi vedi fino a domani pomeriggio non è che non voglio risponderti, solo che non ci sono

Figurati, non ti preoccupare!
In ogni caso mi sembra di capire che ormai le posizioni siano abbastanza cristallizzate, forse non è il caso che io continui ad annoiare i lettori ripetendo sempre le stesse cose! ?
Scherzi a parte, ne approfitto per dire che ho apprezzato molto il modo in cui ti sei messo a disposizione in questa discussione!

 

[BAT]

rispondo velocemente perché devo andare a lavorare

sui calcoli nulla da eccepire, ma, mi duole ammetterlo, la conclusione che ne trai
non mi convince più di tanto

il numero mostrato è la probabilità che escano 6 numeri (particolari) da una estrazione totalmente casuale (perché tutte le sestine devono essere equiprobabili), un evento che potrebbe essere simulato da un generatore casuale perfetto.

Partiamo da un array oridnato da 1 a 90; un generatore pseudorandom può, prima o poi (al crescere del numero di estrazioni), generare una sequenza di indici come quella menzionata, ma in questo caso dovrebbe farlo esattamente nelle prime 6 estrazioni; a seconda dell'implementazione del randomizzatore, potrebbe anche succedere, tuttavia in tal caso sarebbero altre le sestine a non essere equiprobaili a 1-2-3-4-5-6. E' una cane che si morde la coda, se il generatore non è perfetto l'equiprobailità delle sestine è impossibile (per ottenere qualcosa che ci assomiglia un po' di più serve un numero molto elevato di scambi, dove un numero che cambia posto nell'array potrebbe cambiare di posto nuovamente ad una estrazione successiva).

[EDIT del pranzo]
se l'array di partenza è ordinato manca l'aleatorietà, bisogna partire da una array disordinato (generato in modo pseudocasuale);
se l'array è disordinato (=il mazzo/urna è stato mischiato) le successive 6 estrazioni casuali portano la sestina a inizio array (estrazioni senza reimbussolamento) e sono un risultato accettabile.