Dotaz: C++ generování náhodného pořadí

[krb]

Zdravím, je možné nějak udělat, aby program náhodně generoval pořadí spouštění mnou vytvořených funkcí? Děkuji

Odpovědi

[Kit]

Třeba nějaký random generátor a switch by nestačil?

[Radovan]

A pokud má být každá funkce spuštěná jen jednou nebo maximálně nekolikrát, stačí přidat flag nebo čítač.

[Kit]

Tak do toho bych nešel. Pokud by byla tato podmínka, použiji algoritmus míchání karet, tedy vygeneruji pole a každý prvek prohodím s náhodným prvkem. Pak sekvenčně projdu pole.

[l4m4]

To je hodně mizený algoritmus, protože generuje různá pořadí s velmi odlišnými pravděpodobnostmi. A to i pro velmi malý počet prvků (tedy od 3 výše), kdy ještě zdaleka není problém s tím, že celkový počet permutací je srovnatelný nebo větší než počet různých stavů generátoru.

Normálně se náhodná permutace generuje postupným náhodným vybíráním z pole, přičemž vybraný prvek se vždy smaže a pole zkrátí (to lze udělat efektivně výměnou s posledním prvkem), dokud v poli něco je.

Míchání lze použít, ale pro dostatečnou náhodnost musí být počet zamíchání větší než počet prvků pole. Kolikrát, to je funkce velikosti pole (a požadované uniformity pravděpodobnosti), která se dá vygooglit...

[AraxoN]

Práve naopak - volá sa to Knuth shuffle, má to rovnakú pravedpodobnosť každej permutácie a lineárnu zložitosť.

[l4m4]

Knuth shuffle je ovšem něco jiného než ,každý prvek prohodím s náhodným prvkem`.

[AraxoN]

Tak som si to poriadne pozrel a dávam Ti za pravdu. Nie je to Knuth shuffle a nemá to rovnakú pravdepodobnosť každej permutácie. Idem si na hlavu sypať popol...

[Kit]

Tak si to přečti ještě jednou a zjistíš, že je ten algoritmus stejný. Jen to míchání děláme v různý okamžik. Negeneruji dvě náhodné pozice, ale jeden index mám v cyklu a druhý generuji.

[l4m4]

Ano, o tom přesně mluvím, takhle to dělat nejde. Ach jo.

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Implementation_errors

[Kit]

Jenže oni v tom algoritmu mají chybu. Já ten obor generovaných hodnot nesnižuji. Prostě všechny náhodné indexy generuji v rozsahu 1..N, kde N je celkový počet prvků. A to je rozdíl.

[l4m4]

Ano, to je ten rozdíl, který způsobuje, že to máš blbě. Vezmi si pět prvků, nech si vygenerovat deset milionů permutací a podívej se na rozdělení. Relativní odchylky četností všech permutací od 1/120 musejí být několik promile.

[Radovan]

Já na míchání karet používám něco jiného, prostě generuji náhodná čísla a zjišťuji jestli už jsou v poli. Pokud ano, přičtu 1 a projedu to znovu... Je to podstatně rychlejší než kdyby se mělo generovat opakovaně, zvlášť ke konci míchání Ale až budu mít náladu tak to s tím tvým schválně zkusím poměřit.

Jinak jsem reagoval přímo na ten switch, s ním by to byla asi nejjednodušší možnost. A asi i nejméně paměťově náročná, zvlášť u nějakého bitového pole.

[Jendа]

Nehromadí se ti pak ke konci pole vyšší čísla? Tedy jestli jsem to správně pochopil.

[Michal Kubeček]

Pokud pod "přičtu jedna" rozumíme, že po posledním prvnku následuje první, tak nebudou. V pořádku ten algoritmus ale není, protože pokud například budeme takhle míchat čísla 1-20 a v prvních sedmi kolech vybereme 5,1,7,9,2,8,6, bude mít v dalším kole desítka pravděpodobnost výběru 6/20, trojka 3/20 a zbylých jedenáct 1/20.

[Radovan]

Máš pravdu, v pořádku to skutečně není.

Příklad: budu míchat deset karet, prvních osm už jsem použil a zbývají mi poslední dvě, s čísly 9 a 10. Mám šanci že se trefím do osmi vylosovaných nebo devítky 9/10, zatímco u desítky je to jen 1/10. Nejlepší by byl zmenšující se seznam dosud nepoužitých čísel a losovat z něj.

[l4m4]

No hurá, dostáváme se k tomu, co jsem napsal na začátku (což samozřejmě není nic jiného než Knuth shuffle, akorát jsem ho zvyklý psát ,odzadu`, protože mi tak přijde názornější).

[Radovan]

Ještě nejásej, ono v Sinclair BASICu na Didaktiku Gama jsem si nemohl kdovíjak vyskakovat, takže jsem se holt musel smířit s tím že sice zvýším rychlost, ale snížím náhodnost. Ale s ní to také nebylo až tak zlé, ono tady záleží především na kvalitě generátoru náhodných čísel

[Sten]

Hlavně záleží na tom, jak moc velkou náhodnost pro svou aplikaci potřebujete, něco je míchání karet pro simulátor mariáše a něco úplně jiného generování X.509 certifikátu

[l4m4]

Knuth shuffle je ale prohazování in-place a potřebuje n-1 náhodných čísel, kde n je počet prvků pole. To se moc zlepšit nedá.

[Radovan]

Asi takhle?

10 pocet = 52
20 dim pole(pocet)
30 for i = 1 to 52 : pole(i) = i : next i
40 if pocet < 1 then goto 90
50   n = int(rnd(1)*pocet)+1
60   w = pole(pocet) : pole(pocet) = pole(n) : pole(n) = w
70   pocet = pocet-1
80   goto 40
90 for i = 1 to 52 : print pole(i), : next i
100 print : end

Tak s tím se ten můj obrácený bubblesort fakt srovnávat nedá

10 pocet = 52
20 dim pole(pocet)
30 for i = 1 to 52
40   n = int(rnd(1)*pocet)
50   n = n+1 : if n > 52 then n = 1
60   for j = 1 to i
70     if pole(j) = n then goto 50
80   next j
90   pole(i) = n
100 next i
110 for i = 1 to 52 : print pole(i), : next i
120 print : end

[Radovan]

Nikoliv, ke konci pole se mi hromadí dosud nepoužitá čísla Prostě najdu nejbližší které je ještě volné a to použiji místo toho vylosovaného použitého. Ono by to mohlo stejně tak fungovat i opačně, s odčítáním, ale takhle se jednodušeji dělá modulo při přetečení.

[Roman Došek]

Co takhle uložit do pole ukazatele na funkce a pak na to pole zavolat RandomSort :)

Pak už stačí volat postupně funkce z pole...

[vain]

Přesně to mě napadlo, když jsem to četl, asi nejjednodušší řešení.

[l4m4]

To je úžasná rada, ještě tak kdyby v libstdc++ nějaký RandomSort byl...

(Existuje ovšem random_shuffle().)

[vain]

Nemyslel jsem nějaký RandomSort, ale pole ukazatelů na funkce. S tím už může dělat potom cokoliv.

[Matlák]

ono je technicky jedno jestli máš pole ukazatelů na funkce, jednu "rozdělující" funkci a pole integerových konstant značících "pořadí" funkce a nebo třeba jestli přičítáš k adrese té funkce náhodné číslo vynásobené předem zjištěnou délkou funkce v paměti

[vain]

Asi je, ale pole ukazatelů na funkce mi přijde estetičtější

[vencas]

random_shuffle je přesně co je v tomto případě potřeba, ne?