Crea il tuo forum GRATIS su GlobalFreeForum.com.

Algoritmi di mescolamento

In questa sezione avverranno le discussioni sulla scienza e sulle arti. Si possono chiedere pareri e spiegazioni o postare i propri pensieri a riguardo di un argomento. Qui potete postare spiegazioni su un qualsiasi argomento: matematica, chimica, lingue etc...

Moderatori: Gruppo Admin, Gruppo Mod

Algoritmi di mescolamento

Messaggioda Style { HdS619 } » 10/07/2012 - 16:08

Con l'ultimo programma realizzato mi son trovato nella condizione di dover "mescolare" degli elementi, quindi per chi ne avesse bisogno scrivo qualcosina che può tornare utile.

Gli algoritmi di mescolamento, in inglese "Shuffling algorithms", sono degli algoritmi utilizzati quando si hanno una serie di elementi ( ad esempio un mazzo di carte ) e li si voglia mescolare in modo che il loro ordinamento sia casuale, da un punto di vista matematico sono delle permutazioni casuali.
Uno degli algoritmi più comuni è il "Fisher-Yates shuffle" ( che ho casualmente implementato, avendolo scritto prima di cercare informazioni ) ed è molto semplice, dal punto di vista generale una sua implementazione può avvenire così:

  • Si inseriscono gli elementi da ordinare in una lista da 1 a N ( dove N è il numero complessivo di elementi da mescolare )
  • Si genera un numero K casuale compreso nel range 1-N
  • Si scambia il primo elemento della lista con il K-esimo elemento
  • Si ripete dal punto 2 da un minimo di N volte ad un massimo a scelta

In questo modo si ha la lista con gli elementi disposti casualmente. Naturalmente questo algoritmo può essere modificato per adattarlo alle varie esigenze, ad esempio il range invece di essere da 1 a N si può prendere da I a J ( con I e J due numeri a scelta compresi nel range 1 - N ) spostando così il range solo ad una porzione della lista e mescolando solo una parte degli elementi.
Naturalmente più alto è il numero di permutazioni ( ovvero più volte si ripetono i punti 2-3 ) maggiore sarà il mescolamento.

Immagine
Fine. :)
Il mio sito personale

Without freedom of choice there is no creativity.
Without creativity, there is no life.


---
Ogni volta che usi un goto un unicorno muore. - Flame Alchemist
Avatar utente
Style { HdS619 }
Gold Member
Gold Member
 
Messaggi: 3073
Iscritto il: 12/05/2007 - 18:30
Località: Lecce

Re: Algoritmi di mescolamento

Messaggioda Flame_Alchemist » 11/07/2012 - 14:18

Secondo me non funziona correttamente. Nel senso che alcune permutazioni sono più probabili di altre (in particolare questo è vero se si ripete lo shuffling poche volte, se si incrementa il limite a 10*N comincia a dare i risultati voluti).

L'algoritmo che ho in mente io è una cosa tipo (c'è un'implementazione nel codice sotto):
1. elemento i del vettore
2. k = casuale tra i e n
3. swap v[k], v[i]
(che risulta abbastanza simile a quello di Knuth in TAOCP, vol 2, solo che lui scandisce il vettore al contrario e genera k tra 0 e i)
Di questo (ad occhio) penso che una dimostrazione di correttezza sia abbastanza semplice.

In un caso simile al tuo, ma non uguale, che può essere schematizzato così:
Codice: Seleziona tutto
for i in V:
    K = random(0, length V)
    swap (V[i], V[K])

che sarebbe l'algoritmo più naive in assoluto, si può vedere in fretta che non produce i risultati sperati. Genera N^N permutazioni ma solo N! sono distinte (che sono di meno). N^N non divide N! (dimostrazione lasciata come esercizio), quindi alcune permutazioni sono più frequenti di altre.

Come interessante nota storica: fino a non molti anni fa (boh, primi 2000) molte società di poker online implementavano questo metodo per mischiare le carte (e lo rendevano pubblico sul loro sito per dimostrare che utilizzavano un metodo onesto), quindi chi lo sapeva poteva farci molti soldi (si scopre che, per esempio, le permutazioni che iniziano con 2 sono più comuni di quelle che iniziano con 1).

Un piccolo (e orrendo, lo so, ma abbiate pazienza, l'ho buttato giù in poco tempo e C non è mai stato il mio pane quotidiano, ma serviva qualcosa con brevi tempi di esecuzione) codice per verificare quello che ho detto finora.
Codice: Seleziona tutto
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LIMIT 1000000

void shuffle_style(int *a, int n, int times)
{
    int K, i, tmp;
    for (i=0;i<times;i++) {
        K = rand()%n;
        tmp = a[K];
        a[K] = a[1];
        a[1] = tmp;
    }
}

void shuffle_knuth(int *a, int n)
{
    int K, i, tmp;
    for (i=0;i<n;i++) {
        K = (rand()%(n-i))+i;
        tmp = a[K];
        a[K] = a[i];
        a[i] = tmp;
    }
}

int main()
{
    int a[] = {1, 2, 3};
    int i, s, m, t;
    t = LIMIT/6;
    s = 0;
    m=0;
    srand(time(NULL));
    for (i=0;i<LIMIT;i++)
    {
        a[0] = 1; a[1]=2;
        a[2]=3;
        shuffle_style(a, 3, 3);
        if (a[0]*100+a[1]*10+a[2] == 213)
            s++;
    }
    for (i=0;i<LIMIT;i++)
    {
        a[0] = 1; a[1]=2;
        a[2]=3;
        shuffle_knuth(a, 3);
        if (a[0]*100+a[1]*10+a[2] == 213)
            m++;
    }
    printf("Teorico: %d, Style: %d Knuth: %d", t, s, m);
    return 0;
}
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Algoritmi di mescolamento

Messaggioda Al_Chiappone » 11/07/2012 - 14:46

Discussione interessante, provo a dire la mia.

Nei lontani anni '80 scrissi un programma per giocare a poker con il Commodore64 e dovetti affrontare anche io questo problema. La soluzione è quella di un adolescente con poche conoscenze informatiche ma credo che l'idea sia abbastanza valida:

1) crea una struttura di dati che contiene il valore della tua carta ed un campo intero extra (chiamiamolo tag)
2) per ogni carta del tuo mazzo assegna a tag un valore casuale compreso tra 0 e INT_MAX
3) ordina le carte per tag crescente (o decrescente)

Questo metodo ha complessità O(N*logN) indipendentemente dalla qualità del mescolamento.
Avatar utente
Al_Chiappone
Gold Member
Gold Member
 
Messaggi: 667
Iscritto il: 18/11/2007 - 11:25
Località: Rio de Janeiro - RJ - Brasile

Re: Algoritmi di mescolamento

Messaggioda Style { HdS619 } » 11/07/2012 - 15:08

Molto interessante il tuo metodo Al_Chiappone, l'unica pecca è l'utilizzo forzato di una struttura ma niente di terribile :)

Invece a me è rimasto un dubbio, praticamente la differenza tra quella cosa che ho implementato io del tipo Fisher-Yates e la variante di Knuth è che nel primo caso è necessario eseguire un numero di permutazioni maggiori o uguali a N ( preferibilmente maggiori per ottenere un buon mescolamento ), mentre con Knuth sono sufficienti N permutazioni?
Il mio sito personale

Without freedom of choice there is no creativity.
Without creativity, there is no life.


---
Ogni volta che usi un goto un unicorno muore. - Flame Alchemist
Avatar utente
Style { HdS619 }
Gold Member
Gold Member
 
Messaggi: 3073
Iscritto il: 12/05/2007 - 18:30
Località: Lecce

Re: Algoritmi di mescolamento

Messaggioda Flame_Alchemist » 11/07/2012 - 16:05

Nella tua versione (che non credo sia una variante di Fisher-Yates, però non ho particolari informazioni su questo metodo) è necessario eseguire un numero maggiore di iterazioni del procedimento (idealmente molto maggiori, si dovrebbe fare qualche prova con numeri grandi per essere sicuri, ma penso che ci debba essere almeno un fattore 10). Ma credo che sia un side-effect.

Mi spiego meglio: se tu applichi molte volte in maniera iterativa allo stesso vettore l'algoritmo naive che ho scritto sopra ottieni comunque un buon risultato (nel senso che le frequenze delle varie permutazioni sono come dovrebbero essere). Credo che con il tuo algoritmo si abbia lo stesso "problema". (Puoi verificarlo anche dal programma lì sotto, togliendo il codice per la reinizializzazione del vettore dal ciclo for).
Questo succede perché applicando una permutazione ad un insieme già stato permutato ottieni un'altra permutazione, e quindi alla fine tutto si bilancia.

Fisher-Yates e Knuth sono praticamente lo stesso algoritmo; la versione di Knuth è ottimizzata (credo che nelle nuove versioni di TAOCP sia scritto che l'algoritmo originario era di Fisher-Yates, io probabilmente ne ho una vecchia).
La versione che ho scritto io lì sopra è abbastanza simile, e si comporta allo stesso modo. Siamo O(N) in tempo e O(1) in spazio (facciamo tutto in-place).
Invece il metodo di Al è l'altro metodo più usato, chiaramente il tempo di esecuzione dipende dall'algoritmo di ordinamento implementato, quindi se siamo bravi O(N lg N) e O(n) per spazio.

Tornando un secondo sull'argomento dei siti di poker, ovviamente la qualità dello shuffling non sarà data solo da l'algoritmo usato ma anche dal metodo di generazione di numeri casuali, che può veramente diventare il collo di bottiglia, in questi casi.
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Algoritmi di mescolamento

Messaggioda skary » 15/07/2012 - 00:35

Mmm interessanti gli algoritmi proposti.

Io ne avevo utilizzato uno a suo tempo, ma non sono proprio certo della sua casualità.

Funzionava più o meno così :

Se ho N elementi da mescolare, allora genero un bitarray di N bit a 0, dopo di che genero un numero casuale i, controllo lo stato del bit iesimo del bitarray.
Se il bit iesimo è zero allora lo pongo ad uno ed accodo alla lista risultato l'iesimo elemento della lista di entità da mescolare.
Se il bit iesimo è uno allora genero un valore booleano in maniera casuale, se è true inizio a scorrere il bitarray verso sinistra altrimenti verso destra, scorrendolo in modo da avere un j = i++ ad ogni passo (o i-- a seconda del risultato del booleano), quando il bit jesimo del bitarray è finalmente 0 lo pongo ad 1 e prendo l'elemento jesimo e lo accodo alla lista risultato.
Ovviamente scorro il bitarray in modo ciclico ( arrivato a zero se decremento j passo al valore massimo e da quello massimo se incremento j arrivo a zero).

Per ottimizzare il tutto si possono anche stratificare i bitarray di modo da velocizzare lo scorrimento, banalmente se il bitarray è composto da integer o char (in questo caso sarebbe più performante con gli integer ma mi trovo meglio ad usare unsigned char perché riesco a caricare facilmente in memoria un sacco di maschere binarie utili per le operazioni da intraprendere) prima di scandire il successivo blocco di 32 bit (caso in cui consideri il bitarray come composto da unsigned integer) del bitarray controllo che sia minore di quattro miliardi circa (il massimo valore di un unsigned int) qual'ora non fosse è inutile cercare uno zero, pertanto passo al blocco successivo.
In caso abbia moltissimi elementi, sacrificando un po di memoria si possono creare proprio alberi di bitarray (purtroppo la faccenda a livello di codice si fa tremendamente complicata).
Immagine

Le persone ottimiste credono che il nostro universo sia magnifico e che non vi sia modo migliore di vivere.
I pessimisti semplicemente temono che gli ottimisti abbiano ragione.
Avatar utente
skary
Utente
Utente
 
Messaggi: 1449
Iscritto il: 19/07/2007 - 21:58


Torna a Il Pozzo della conoscenza

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron