Probleme din lumea reală cu amestecarea naivă

Am scris o serie de articole menite să predea conceptele de programare începând cu utilizarea subiectelor legate de poker. În prezent, lucrez la subiectul amestecării.

Așa cum Jeff Atwood indică pe CodingHorror.com , o singură metodă de amestecare (iterând printr-o matrice și schimbând fiecare carte cu o cartelă aleatoare în altă parte a matricei) creează o distribuție neuniformă a permutărilor. Într-o aplicație actuală, aș folosi doar Knuth Fisher-Yates shuffle pentru o mai multă uniformitate uniformă. Dar, nu vreau să scriu o explicație a conceptelor de programare cu algoritmul mult mai puțin prietenos cu coderul.

Acest lucru conduce la întrebarea: Cât de mult ar avea un avantaj o pălărie de negru dacă știau că folosiți un amestec naiv al unui pachet de 52 de cărți? Se pare că ar fi infinit de mic.

0

5 răspunsuri

Schimbarea intitulat este o schimbare nesemnificativă în comparație cu shuffle naiv: Doar swap cu orice carte în secțiunea rămasă (unshffled) a punții în loc de nicăieri în întreaga punte. Dacă vă gândiți la acest lucru ca alegerea repetată a următorului card în ordine din cărțile rămase neschimbate, este și destul de intuitivă.

Personal, cred că predarea studenților unui algoritm sărac atunci când cel mai potrivit nu este mai complicat (și mai ușor de vizualizat!) Este o abordare proastă.

0
adăugat
Sunt de acord. În acest caz, cred că ar trebui prezentate atât algoritmi, cât și o explicație a motivului pentru care unul este mai bun decât celălalt. În acest caz, este o schimbare foarte mică și, în opinia mea, nu o face mai complicată.
adăugat autor some, sursa

Doar ca o parte, a existat o post pe blog pe ITtoolbox despre mișcarea care ar putea fi de interes atunci când vine vorba de simularea unui shuffle.

În ceea ce privește întrebarea dvs., considerați că există 52! punctele de configurare pe care ar trebui să le porniți cu care ar putea juca un rol în cazul în care lucrurile se așează ca în exemplul lui Jeff al pachetului de 3 cărți, rețineți că 1 în suprareprezentat are loc în fiecare slot o dată. De asemenea, rețineți că spune că va trebui să aveți câteva mii de exemple înainte de a se vedea unde este avantajul, dar cu o punte nu este probabil să începeți din nou cu aceeași punte inițială, nu-i așa? Ați lua cardurile împărțite și le-ați pus pe fundul lor și le-ați amestecat pe cele pe care nu le-aș putea repeta.

0
adăugat

Nu înseamnă că scrieți un program de poker care va fi utilizat pentru un site real de jocuri de noroc online. O abilitate pentru cineva de a cheat la program nu este o afacere mare atunci când îi înveți pe oameni cum să programeze.

Lăsați o notă care să spună că acesta este un model slab al lumii reale (cu referire la acesta ca o posibilă eroare de securitate) și pur și simplu continuați cu învățătura.

0
adăugat
Nu am avut, în momentul în care am scris asta, am realizat că diferența este atât de banală. Aș fi de acord: spuneți-le algoritmului de amestecare bun. Poate că detaliile exacte despre "de ce" pot fi "se referă la această literatură".
adăugat autor Keith B, sursa
Nu, dar oamenii care citesc aceste articole pot merge mai departe. Obținerea unei amestecări corecte este importantă, deoarece a face greșit a provocat o pauză înainte.
adăugat autor afrazier, sursa

Subjective.

Se pare că ar fi infinit de mic.

De acord.

0
adăugat

It turns out the advantage is quite significant. Check out this article

O parte a problemei este algoritmul defect, dar o altă parte este presupunerea că puteți obține numere "aleatoare" de pe un computer.

0
adăugat