Hvordan fungerer "shuffle" / tilfeldighetsalgoritmer?

[Rescue me]

Enkelt og greit, hvordan fungerer "shuffle" / tilfeldighetsalgoritmer?

 

Er det noen som har kommet opp med en helt sykt bra slik algoritme?

[nicho_meg]

http://en.wikipedia.org/wiki/Random_number_generation forklarer vel det meste.

Som regel er slike enkle shuffle-algoritmer psedo-tilfeldige. Dvs. at de ser tilfeldige ut, men egentlig er de deterministiske. Så om man bruker tidsstempel som "seed" så vil man alltid få samme resultat om man starter på samme tid. Bakgrunnstøy fra universet er derimot "ekte tilfeldig" og vil gi helt tilfeldige resultat om det er nødvendig.

Her er et mål på hvor god en slik tilfeldighetsalgoritme er: http://en.wikipedia.org/wiki/Diehard_tests

 

For å lage en shuffle-funksjon så gir man bare hver sang (etc.) et tall og sorterer den etter hvilke tall tilfeldighetsalgoritmen gir deg.

[delfin]

http://en.wikipedia.org/wiki/Random_number_generation forklarer vel det meste.

Som regel er slike enkle shuffle-algoritmer psedo-tilfeldige. Dvs. at de ser tilfeldige ut, men egentlig er de deterministiske. Så om man bruker tidsstempel som "seed" så vil man alltid få samme resultat om man starter på samme tid. Bakgrunnstøy fra universet er derimot "ekte tilfeldig" og vil gi helt tilfeldige resultat om det er nødvendig.

Her er et mål på hvor god en slik tilfeldighetsalgoritme er: http://en.wikipedia.org/wiki/Diehard_tests

 

For å lage en shuffle-funksjon så gir man bare hver sang (etc.) et tall og sorterer den etter hvilke tall tilfeldighetsalgoritmen gir deg.

 

Ja, det er helt riktig "random" i vanlig programmering er pseudorandom og bruker millisekunder som seed, men i de fleste praktiske sammenhenger er det nok, da hvert millisekund som passerer vil gi en ny rekke av tall som er "tilfeldig". Det finnes en del muligheter for å finne "ekte" tilfeldige tall, f.eks bakgrunnsstøy fra universet som nevnt, men i praksis er "pseudo-random" nok til de aller fleste oppgaver..

 

Litt om algoritmene fra wikipedia og en ekte hardware "random"-generator

[''']

Denne algoritmen er optimal for å stokke om en tabell: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

 

Den forutsetter at du har en tilfeldig-tall-generator som beskrevet i linkene over.

[Gjest Slettet+5132]

Kan veldig lite om programnering og slikt, men shufflefunksjonen Microsoft bruker i Xbox Play er ubrukelig.

[Djn]

Hvis man trenger en uendelig "shuffle"-playlist trukket fra en haug med sanger, er det enkleste å først trekke f.eks. ti sanger, og så plukke en tilfeldig ny sang og putte den på slutten av listen hver gang man har spilt ferdig en. For å slippe å få den samme sangen to ganger på rad kan man f.eks. trekke på nytt om man får en sang som alt er køet opp - forutsatt at det er nok sanger å ta av.

 

Hvis du derimot skal spille av et album (eller generelt en kort liste sanger) slik at du får alle én gang, men i en tilfeldig rekkefølge, er det bedre å stokke om den komplette listen med sanger. Den metoden Grønnsyre linket er bra - lett å forstå/skrive, resultatet er like tilfeldig eller ikke som de tilfeldige nummerene du bruker. Grei å forklare, også:

 

Start med en tom spilleliste A, og en liste med sanger som skal spilles B.

Plukk en tilfeldig sang fra B, flytt den til A.

Repeter til B er tom.

A er nå alle sangene fra B, i en tilfeldig rekkefølge.

 

Den første metoden fungerer bedre hvis du har upraktisk mange sanger - og hvis listen kan endre seg mens du spiller av. Den andre er enklere, garanterer at du får hele albumet en gang, og kan la deg se hele rekkefølgen med en gang (i stedet for å alltid vise de neste f.eks. 10), men kan ikke brukes til å lage endeløse rekker av tilfeldige sanger.

Endret 24. april 2014 av Djn

[Djn]

For det rent praktiske om hvordan man genererer "tilfeldige" nummer - du kan prøve deg på paperet om Yarrow, som er en ganske populær metode, eller et bokkapittel om Fortuna, som er nyere.

Endret 25. april 2014 av Djn