Fišer–Jetsovo mešanje

Fišer–Jetsovo mešanje je algoritam koji generiše nasumične permutacije konačnog niza, uprošćeno, taj algoritam meša niz. Efektivno, algoritam stavlja sve elemente u šešir; kontinuirano određuje sledeći element tako što nasumično izvlači element iz šešira dok ne ostane nijedan. Taj algoritam proizvodi nepristrasne permutacije: svaka permutacija je podjednako verovatna. Moderna verzija ovog algoritma je efikasna: vreme koje mu je potrebno je proporcionalno broju elemenata koji se mešaju i meša ih u mesto.

Fišer–Jetsovo mešanje je nazvano po Ronaldu Fišeru i Frenku Jetsu koji su ga prvi opisali a takođe je poznato i kao Knut mešanje po Donaldu Knutu. Varijacija Fišer–Jetsovo mešanje, poznata kao Satolov algoritam, se može koristiti za generisanje nasumičnih cikličnih permutacija dužine n umesto nasumičnih permutacija.

Originalna Fišer-Jetsova metoda

Fišer–Jetsovo mešanje u svojoj originalnoj formi su 1938. opisali Ronald Fišer i Frenk Jets u svojoj knjizi Statističke tabele za biološka, poljoprivredna i medicinska istraživanja. Njihov opis algoritma je koristio olovku i papir; tabela sa nasumičnim brojevima je omogućavala nasumičnost. Osnovni metod za generisanje nasumičnih permutacija brojeva od 1 do N sledi:

1. Napiši brojeve od 1 do N.
2. Izaberi nasumični broj k.
3. Računajući sa donjeg kraja, precrtaj redni broj k.
4. Ponavljajte od koraka 2 dok se ne izbrišu svi brojevi.
5. Niz brojeva zapisan u koraku 3 je sada nasumična permutacija originalnih brojeva.

Pod uslovom da su nasumični brojevi izabrani u koraku 2 iznad zaista nasumični i nepristrasni, takva će biti i rezultujuća permutacija.Fišer i Jets su pažljivo opisali kako da se dobiju takvi nasumični brojevi u bilo kom željenom rasponu iz priloženih tabela na način koji izbegava ikakvu pristrasnost. Takođe su predložili mogućnost korišćenja prostije metode-odabir nasumičnih brojeva od 1 do N uz odstranjivanje duplih brojeva - kako bi se generisala prva polovina permutacije i primenjivanje složenijeg algoritma samo na drugu polovinu gde bi odabir duplog broja postao frustrirajuće čest.

Moderni algoritam

Modernu verziju Fišer–Jetsovo mešanja, dizajniranu za upotrebu na računarima, je 1964. uveo Ričard Durstenfeld, a popularnom je učinio Donald E. Knut u Umetnost računarskog programiranja kao „Algoritam P (mešanje)“. Ni Durestenfeldovi članci ni Knutovo prvo izdanje Umetnost računarskog programiranja nisu odali priznanje Fišer-u i Jetsu za njihov rad; možda nisu bili toga svesni. Sledeća izdanja Knutovog Umetnost računarskog programiranja Fišerov i Jetsov doprinos.

Algoritam koji je opisao Durstenfeld se malo razlikuje od onoga koji si dali Fišer i Jets, ali je ta razlika značajna. Dok bi izvorna računarska implementacija Fišer-Jets metode traćila vreme brojeći preostale brojeve u koraku 3 iznad, Durstenfeldovo rešenje je da se  pomere precrtani brojevi na kraj liste pri čemu menjaju mesta sa poslednjim neprecrtanim brojem pri svakoj iteraciji. Ovo smanjuje subeksponencijalno vreme algoritma na ${\mathcal {O}}(n)$, u odnosu na ${\mathcal {O}}(n^{2})$ iz originalne  naivne implementacije. Ova promena daje sledeći algoritam (za niz zasnovan na nuli).

-- За мешање низа а од n елемената (индекси 0..n-1):
за i од n−1 до 1 
     j ← случајни цели број такав да 0 ≤ j ≤ i
     exchange a[j] and a[i]

Ekvivalentna verzija koja meša niz u suprotnom smeru (od najnižeg indeksa do najvišeg) je:

-- За мешање низа а од n елемената (индекси 0..n-1):
за i oд 0 до n−2
     j ← случајни цели број такав да i ≤ j < n
     exchange a[i] and a[j]

Primeri

Metoda olovka i papir

Kao primer, permutovaćemo brojeve od 1 do 8 koristeći originalnu Fišer–Jetsovo metodu. Počećemo ispisivanjem brojeva na papiru:

Opseg	Izvučeni	Precrtani	Rezultat
		1 2 3 4 5 6 7 8

Sada izvlačimo nasumičan broj k od 1 do 8 – neka to bude 3 – i precrtamo k-ti broj na papiru a zapišemo ga kao rezultat:

Opseg	Izvučeni	Precrtani	Rezultat
1–8	3	1 2 3 4 5 6 7 8	3

Sada biramo sledeći nasumični broj, ovog puta od 1 do 7: izgleda da je to 4. Sada precrtamo četvrti brojkoji još nije već precrtanu delu tabele sa precrtanim brojevima – to je broj 5 – i dodamo ga rezultatu:

Opseg	Izvučeni	Precrtani	Rezultat
1–7	4	1 2 3 4 5 6 7 8	3 5

Sada biramo sledeći nasumični broj od 1 do 6 a zatim od 1 do 5 i tako dalje uz ponavljanje prethodnog procesa precrtavanja:

Opseg	Izvučeni	Precrtani	Rezultat
1–6	5	1 2 3 4 5 6 7 8	3 5 7
1–5	3	1 2 3 4 5 6 7 8	3 5 7 4
1–4	4	1 2 3 4 5 6 7 8	3 5 7 4 8
1–3	1	1 2 3 4 5 6 7 8	3 5 7 4 8 1
1–2	2	1 2 3 4 5 6 7 8	3 5 7 4 8 1 6
		1 2 3 4 5 6 7 8	3 5 7 4 8 1 6 2

Moderna metoda

Sada ćemo uraditi istu stvar koristeći Durstenfeldovu verziju algoritma: ovog puta, umesto precrtavanja izabranih brojeva, a zatim kopiranja, mi ćemo iz zameniti sa poslednjim brojem koji još uvek nije izabran. Počećemo pisanjem brojeva od 1 do 8 kao pre:

Opseg	Izvučeni	Precrtani	Rezultat
		1 2 3 4 5 6 7 8

Za naše prvo izvlačenje dobijamo nasumični broj od 1 do 8: ovog puta to je 6. Zamenjujemo šesti i sedmi broj na listi:

Opseg	Izvučeni	Precrtani	Rezultat
1–8	6	1 2 3 4 5 8 7	6

Sledeći nasumični broj izvlačimo u opsegu 1 do 7, i izgleda da će taj broj biti 2. Tako da, zamenjujemo drugi i sedmi broj i nastavljamo:

Opseg	Izvučeni	Precrtani	Rezultat
1–7	2	1 7 3 4 5 8	2 6

Sledeći broj koji izvlačimo je iz opsega od 1 do 6 i to je 6. To znači da ostavljamo šesti broj na listi (koji je, posle zamene iznad, broj 8) na isto mesto i samo prelazimo na sledeći korak. Ponovo, nastavljamo na isti način dok se permutacija ne završi:

Opseg	Izvučeni	Precrtani	Rezultat
1–6	6	1 7 3 4 5	8 2 6
1–5	1	5 7 3 4	1 8 2 6
1–4	3	5 7 4	3 1 8 2 6
1–3	3	5 7	4 3 1 8 2 6
1–2	1	7	5 4 3 1 8 2 6

I sada se više ništa ne može uraditi tako da je rezultujuća permutacija 7 5 4 3 1 8 2 6.

Varijacije

Naopaki algoritam

Fišer–Jetsovo mešanje , kako ga implementira Durstenfeld, je mešanje u mesto. To jest, sa unapred inicijalizovanim nizom on meša elemente tog niza u mesto, a ne stvara mešanu kopiju tog niza. Ovo može biti prednost ako je niz koji bi trebalo mešati veliki.

Kako bi se simultano inicijalizovao i mešao niz može se postići veća efikasnost korišćenjem naopake verzije mešanja. U ovoj verziji se sukcesivno stavlja element broj i na nasumičnu poziciju među prvim i pozicijama u nizu nakon pomeranja elementa koji je prethodno zauzimao tu poziciju do pozicije i. U slučaju da je nasumična pozicija broj i, ovo " pomeranje" (na isto mesto) uključuje neinicijalizovanu vrednost, ali to nije važno, jer se preko te vrednosti onda odmah prepisuje druga. Nije potrebna zasebna inicijalizacija i ne radi se zamena. U uobičajenim slučajevima gde se izvor definiše nekom prostom funkcijom kao što su celi brojevi od 0 do n − 1, izvor se može jednostavno zameniti funkcijom jer se izvor nikad ne menja tokom izvršavanja.

Да бисте иницијализовали низ а од n елемената насумично премешаном копијом извора, оба заснована на 0:
  за i од 0 до n − 1 
      j ← random integer such that 0 ≤ j ≤ i
      ако j ≠ i
          a[i] ← a[j]
      a[j] ← source[i]

Naopako mešanje može izgledati ispravno kroz indukciju. Pod pretpostavkom savršenog generatora nasumičnih brojeva, svaki od n! različitih nizova nasumičnih brojeva koji se mogu dobiti nasumičnim pozivanjem proizvešće drugačije permutacije vrednosti, tako da se one dobijaju samo jednom. Uslov koji proverava da li j ≠ i se može zanemariti u jezicima koji nemaju problema pri ocenjivanju neinicijalizovanih vrednosti niza. Ovo eliminiše n uslovne grane po cenu H_n ≈ ln n + γ redundantnih zadataka.

Druga prednost ove tehnike je da n, broj elemenata u izvoru, ne mora da se zna unapred; samo moramo da imamo mogućnost da detektujemo kraj izvornih podataka kada se stigne do tog kraja. Ispod, niz a se gradi iterativno počevši od praznine, a a dužina predstavlja trenutni broj vidljivih elemenata.

Да бисте иницијализовали празан низ а случајно премешаном копијом извора чија дужина није позната:
  while source.moreDataAvailable
      j ← random integer such that 0 ≤ j ≤ a.length
      if j = a.length
          a.append(source.next)
      else
          a.append(a[j])
          a[j] ← source.next

Satolo algoritam

Sličan algoritam je objavila Sandra Sattolo 1986. za generisanje jednako distribuisanih ciklusa (maksimalne) dužine n. Jedina razlika između Dustenfeld i Satolo algoritma je da se u ovom drugom algoritmu, u koraku 2 iznad, nasumični broj j inkluzivno bira iz opsega između 1 i i-1 (pre nego između 1 i i). Ova jednostavna promena menja algoritam tako da se rezultujuća permutacija uvek sastoji od jednog niza.

Zapravo, kao što je ispod opisano, veoma je lako da se 'nehotice' implementira Satolo algoritam kada se planira obično Fisher-Yates mešanje. Ovo će proizvesti pristrasne rezultate tako što prouzrokuje biranje permutacija iz manjeg skupa (n−1)! ciklusa dužine N, umesto iz celog skupa svih n! mogućih permutacija.

Činjenica da Sattolo algoritam uvek proizvodi ciklus dužine n može biti prikazana indukcijom. Indukcijom pretpostavimo da posle početne iteracije petlje, preostale iteracije permutuju prve n−1 elemente prema ciklusu dužine n−1 (te preostale iteracije su samo Sattolo algoritam primenjen na te prve n−1 elemente). Ovo znači da se praćenjem početnog elementa do njegove nove pozicije p, a zatim elementa originalno na poziciji p do njegove nove pozicije i tako dalje samo vraćamo na početnu poziciju nakon posećivanja svih drugih pozicija. Pretpostavimo da je početna iteracija zamenila konačni element sa onim na poziciji k (koja nije kranja) i da je proizilazeća permutacija prvih n−1 elemenata i zatim ga pomerila na poziciju l; mi poredimo permutaciju p svih n elemenata sa tom preostalom permutacijom σ prvih n−1 elemenata. Praćenjem sukcesivnih pozicija kao što je upravo pomenuto, vidi se da ne postoji razlika između p i σ dok se ne stigne do pozicije k. Ali onda, pod π element originalno na poziciji k se pomera na krajnju poziciju a ne na poziciju l, a element originalno na krajnjoj poziciji se pomera na poziciju l. Odatle, niz pozicija za p opet prati niz za σ i sve pozicije će opet biti posećene pre vraćanja na početnu poziciju, kao što se zahteva.

Što se tiče jednake verovatnoće permutacija dovoljno je primetiti da modifikovani algoritam uključuje (n−1)! različitih mogućih nizova nasumično generisanih brojeva od kojih svaki jasno proizvodi različite permutacije i svaki se odvija - pod pretpostavkom da je izvor nasumičnog broja nepristrasan - sa podjednakom verovatnoćom. (n−1)! različite permutacije koje su na ovaj način dobijene precizno iscrpljuju skup ciklusa dužine n: svaki takav ciklus ima jedinstvenu notaciju ciklusa gde je vrednost n na konačnoj poziciji, što omogućava da (n−1)! permutacija preostalih vrednosti ispuni druge pozicije notacije ciklusa.

Primer implementacije Satolo algoritma u Pajtonu je:

random import randrange

def sattolo_cycle(items) -> None:
    """Sattolo's algorithm."""
    i = len(items)
    while i > 1:
        i = i - 1
        j = randrange(i)  # 0 <= j <= i-1
        items[j], items[i] = items[i], items[j]

Poređenje sa drugim algoritmima

Asimptotična kompleksnost vremena i prostora pri Fišer–Jetsovom mešanju je optimalna. U kombinaciji sa nepristrasnim i visoko kvalitetnim izvorom nasumičnih brojeva takođe je zagarantovano generisanje nepristrasnih rezultata. U poređenju sa nekim drugim rešenjima takođe ima prednost da se, ako je potreban samo deo rezultujuće permutacije, može zaustaviti u sred procesa ili se čak može zaustaviti i ponovno pokretati u više navrata pri čemu se permutacije generiše postepeno po potrebi.

Naivna metoda

Naivna metoda zamene svakog elementa sa drugim elementom koji je nasumično odabran iz svih elemenata je pristrasna i u osnovni neispravna. Različite permutacije će imati različite verovatnoće generisanja za svaki $n>2$, jer broj različitih permutacija, $n!$, nejednako deli broj nasumičnih ishoda algoritma, $n^{n}$. Naročito, prema Bertrandovom postulatu biće bar jedan prost broj između $n/2$ i $n$, i ovaj broj će deliti $n!$ ali neće deliti $n^{n}$.

from random import randrange

def naive_shuffle(items) -> None:
    """Наивна метода. Ово је пример шта не треба радити - уместо тога користите Фишер-'Јетса."""
    n = len(items)
    for i in range(n):
        j = randrange(n)  # 0 <= j <= n-1
        items[j], items[i] = items[i], items[j]

Sorti

Alternativna metoda zadaje nasumični broj svakom elementu skupa koji treba mešati a zatim sortira skup prema zadatim brojevima. Metoda sortiranja ima iste asimptotičke kompleksnosti kao Fišer–Jets: iako je generalno sortiranje O(n log n), brojevi se efikasno sortiraju korišćenjem radiks sortiranja u O(n) vremenu. Kao Fišer–Jetsovo mešanje ova metoda sortiranja daje nepristrasne rezultate. Ipak, mora se voditi briga da se zadati brojevi nikad ne dupliraju jer algoritmi sortiranja tipično ne ređaju elemente nasumično u slučaju izjednačenosti. Pored toga, ova metoda zahteva asimptotično veći prostor: O(n) dodatni prostor za skladištenje za nasumične brojeve, u poređenju sa O(1) prostorom za Fišer–Jetsovo mešanje. Konačno, primetno je da metoda mešanja ima jednostavnu paralelnu implementaciju za razliku od Fišer–Jetsovo mešanja, koje je sekventno.

Varijacija metode odozgo je da se meša lista tako što se sortira sa funkcijom poređenja koja daje nasumične vrednosti. Ova varijacija se koristi u jezicima koji podržavaju sortiranje sa funkcijama poređenja koje korisnici određuju. Međutim, ovo je veoma loša metoda: vrlo je verovatno da se dođe do veoma neujednačenih distribucija, što dodatno uveliko zavisi od algoritma za sortiranje koji se koristi. Na primer, pretpostavimo da se quicksort koristi kao sortirajući algoritam, sa fiksnim elementom izabranim kao prvi pivotni element. Algoritam počinje poređenjem pivotnog sa svim ostalim elementima kako bi ih podelio na one manje i one veće od njega, a relativna veličina tih grupa odrediće konačno mesto za pivotni element. Za ujednačeno distribuisanu nasumičnu permutaciju svaka moguća konačna pozicija bi trebalo da bude podjednako verovatna za pivotni element, ali ako svako od početnih poređenja daje 'manje' ili 'veće' sa jednakom verovatnoćom onda će ta pozicija imati binomialnu raspodela za p = 1/2, što daje poziciju blizu sredine niza sa mnogo većom verovatnoćom nego pozicije blizu krajeva. Nasumične funkcije upoređivanja koje se primenjuju na druge metode sortiranja kao što su sortiranje spajanjem mogu dati rezultate koji izgledaju ujednačenije, ali i nisu baš jer spajanje dva niza tako što se ponovno bira jedan od njih sa jednakom verovatnoćom (dok se izbor ne iznudi iscrpljivanjem jednog niza) ne daje rezultate sa ujednačenom distribucijom; umesto toga verovatnoća da se odabere niz bi trebalo da bude proporcionalna broju elemenata koji su preostali u nizu. Zapravno nijedna metoda koja koristi samo dvosmerne nasumične događaje sa jednakom verovatnoćom (bacanje novčića), a koja se ponavlja ograničen broj puta, ne može da ostvari permutacije niza (sa više od dva elementa) sa ujednačenom distribucijom jer svaka linija izvršenja će za verovatnoću imati racionalni broj sa stepenom dvojke kao denominator, dok potrebna verovatnoća 1/n! za svaku moguću permutaciju nije u toj formi.

U principu ova metoda mešanja može čak i da rezultira otkazivanjem programa poput beskrajnih petlji ili krsenja pristupa, jer ispravnost sortirajućeg algoritma može da zavisi od karakteristika odnosa redosleda (poput tranzitivnosti) koje poređenje koje daje nasumične vrednosti sigurno neće imati. Dok se ovakva vrsta ponašanja ne sme događati u sortirajućim rutinama koje nikad ne vrše poređenja čiji se ishodi sa sigurnošću mogu predvideti (zasnovano na prethodnim poređenjima), mogu da postoje validni razlozi za namerno upoređivanje na taj način. Na primer činjenica da bi svaki element trebalo da se poredi kao sebi jednak dozvoljava njihovo korišćenje kao signalnu vrednost zbog efikasnosti, pa ako je to slučaj nasumična funkcija poređenja bi pokvarila sortirajući algoritam.

Mogući izvori pristrasnosti

Mora se voditi računa kada se implementira Fišer–Jetsovo mešanje i pri implementaciji samog algoritma i pri generisanju nasumičnih brojeva na kojima se on gradi. U suprotnom, rezultati mogu pokazati primetnu pristrasnost. Jedan broj uobičajenih izvora pristrasnosti je dat ispod.

Greške u implementaciji

Pristrasnost u redosledu od netačne primene.

Uobičajena greška kada se implementira Fišer–Jetsovo mešanje je da se biraju nasumični brojevi iz pogrešnog opsega. Takav manjkavi algoritam može izgledati normalno ali neće proizvesti svaku moguću permutaciju sa jednakom verovatnoćom, a neke permutacije možda neće uopšte proizvesti. Na primer, uobičajena greška za jedan bila bi odabir indeksa j unosa za zamenu u primeru iznad da uvek bude manji od indeksa i unosa sa kojim se zamenjuje. Ovo menja Fišer–Jetsovo mešanje u Satolo algoritam što proizvodi samo permutacije koje se sastoje od jednog ciklusa koji uključuje sve elemente: naročito, sa ovom modifikacijom, nijedan element niza nikad ne može da završi na svojoj početnoj poziciji.

Slično, stalni odabir j iz celog opsega validnih indeksa nizova sa svakom iteracijom takođe proizvodi pristrasni rezultat mada je to manje uočljivo. Ovo se vidi iz činjenice da se ovakvom primenom dobija nⁿ različitih mogućih nizova zamena gde postoji samo n! mogućih permutacija niza n elemenata. Pošto nⁿ nikad nije jednako deljiv sa n! kada n > 2 (jer je ovaj drugi deljiv sa n−1, koji nema zajedničke proste brojeve sa n), neke permutacije moraju da proishode iz više nⁿ nizova zamena od drugih. Kao konkretan primer ove pristrasnosti primetimo distribuciju mogućih ishoda mešanja niza sa tri elementa [1, 2, 3]. Postoji šest mogućih permutacija ovog niza (3!=6), ali algoritam proizvodi 27 mogućih mešanja (3³ = 27). U ovom slučaju, svaki [1, 2, 3], [3, 1, 2] i [3, 2, 1] rezultiraju sa četiri od mogućih 27 mešanja, dok se svaka od preostale tri permutacije javlja u 5 od 27 mešanja.

Matrica sa desne strane pokazuje verovatnoću svakog elementa na listi dužine 7 koji završava na bilo kojoj drugoj poziciji. Primetite da za većinu elemenata, završavanje na originalnoj poziciji (glavna dijagonala matrice) ima najmanju verovatnoću, a pomeranje za jedno mesto unazad ima najveću verovatnoću.

Modulo pristrasnosti

Fišer–Jetsovo mešanje uključuje odabir diskretnih uniformnih raspodeli celih brojeva iz različitih opsega. Većina generisanih slučajnih brojeva, ipak - bilo pravih ili pseudo-nasumičnih - će samo direktno dati brojeve u određenom opsegu od 0 do RAND_MAX, a u nekim bibliotekama, RAND_MAX može biti nizak i do 32767. Jednostavan i najčešće korišćen način da se takvi brojevi uguraju u željeni opseg je da se primeni modulo operator; to jest, da se podele po veličini opsega i da se uzme ostatak. Međutim, potreba u Fišer–Jetsovo mešanju da se generišu nasumični brojevi u svakom ospegu od 0–1 do 0–n prilično garantuje da neki od ovih ospega neće jednako podeliti prirodni ospeg generatora nasumičnih brojeva. Tako, ostaci neće uvek biti ujednačeno distribuisani i, još gore, pristrasnost će sistematski biti na strani malih ostataka.

Na primer, pretpostavimo da vaš izvor nasumičnih brojeva daje brojeve od 0 do 99 (kao što je to bio slučaj za Fisher-ove i Yates-ove originalne tabele), i da vi želite da dobijete nepristrasni nasumični broj od 0 do 15. Ako jednostavno podelite brojeve brojem 16 i uzmete ostatak videćete da se brojevi 0–3 javljaju oko 17% češće od drugih. To je zato što 16 ne deli 100 jednako: najveći proizvod broja 16 manji ili jednak broju 100 je 6x16=96, a brojevi u nesvršenom nizu 96–99 izazivaju pristrasnost. Najjednostavniji način da se popravi problem je da se odbace ti brojevi pre uzimanja ostatka i da se nastavi sa pokušajima dok se ne pojavi broj u odgovarajućem opsegu. Dok bi ovo u principu, u najgorem slučaju, moglo da traje zauvek, očekivani broj pokušaja će uvek biti manji od jednog.

Pristrasnost poretka zbog netačne primene - n = 1000

Problem u vezi sa ovim se javlja sa implementacijama koje prvo generišu nasumični broj sa pokretnim zarezom - obično u opsegu [0,1), a zatim ga množe veličinom željenog opsega i zaokruže ga. Ovde je problem to što brojevi sa pokretnim zarezom, koliko god oprezno generisani, uvek imaju samo ograničenu preciznost. Ovo znači da postoji samo ograničeni broj mogućih vrednosti sa pokretnim zarezom u bilo kom opsegu, a ako je opseg podeljen na određeni broj segmenata koji ne deli ovaj broj jednako, neki segmenti će završiti sa verovatnijim vrednostima nego drugi. Dok rezultujuća pristrasnost neće pokazati istu sistematsku padajuću tendenciju kao u prethodnom slučaju, ona će i dalje biti tu.

Pseudo-nasumični generatori

Dodatni problem se javlja kada se Fišer–Jetsovo mešanje koristi sa pseudo-nasumičnim generatorom brojeva ili PRNG: pošto je niz brojeva koje takav generator izbaci potpuno određen svojim internim stanjem na početku niza mešanje koje vrši takav generator jednostavno ne može da proizvede više različitih permutacija nego generator koji ima različita moguća stanja. Čak i kada broj mogućih stanja prevazilazi broj permutacija nepravilna priroda mapiranja iz nizova brojeva na permutacije znači da će se neke permutacije javljati češće nego druge. Tako, da bi se smanjila pristrasnost, broj stanja PRNG-a bi trebalo da prevazilazi broj permutacija za najmanje nekoliko redova veličine.

Na primer, ugrađeni pseudo-nasumični generator brojeva u mnogim programskim jezicima i/ili biblioteke mogu imati samo 32 bita internog stanja, što znači da mogu da proizvedu 2³² različitih nizova brojeva. Ako se takav generator koristi da se meša špil od 52 karte, on može samo da proizvede vrlo mali deo 52! ≈ 2^225.6 mogućih permutacija. Moguće je da generator sa manje od 226 bitova internog stanja proizvede sve moguće permutacije špila od 52 karte.

Nijedan pseudo-nasumični generator brojeva ne može da proizvede više različitih nizova, počevši od tačke inicijalizacije, od broja različitih početnih vrednosti. Tako, generator koji ima 1024 bita internog stanja ali koji se inicijalizuje sa 32-bit početnim vrednostima i dalje može da proizvede samo 2³² različitih permutacija odmah nakon inicijalizacije. Može da proizvede više permutacija ako se generator isprobava mnogo više puta pre njegovog korišćenja za generisanje permutacija, ali je ovo veoma neefikasan način povećanja nasumičnosti: pod pretpostavkom da se može srediti da neko iskoristi generator nasumičan broj puta do milijarde, na primer, da pojednostavimo, 2³⁰ puta između inicijalizacije i generisanje permutacija, onda je broj mogućih permutacija i dalje samo 2⁶².

Dodatni problem se javlja kada se koristi prost linearni kongruentni PRNG sa metodom deljenja i uzimanja ostatka za smanjenje opsega koja je opisana iznad. Ovde je problem to što su bitovi nižeg reda linearnog kongruentnog PRNG-a sa modulo 2^e manje nasumični od onih višeg reda: sami niski n bitovi generatora imaju period od skoro 2ⁿ. Kada je delilac stepen dvojke, uzimanje ostatka u suštini znači odbacivanje bitova višeg reda, tako da se dobije znatno manje nasumična vrednost. Drugačija pravila se primenjuju ako linearni kongruentni generator ima modulo sa prostim brojem, ali takvi generatori su retki. Ovo je primer opšteg pravila da će nekvalitetni generatori nasumičnih brojeva ili pseudo-nasumični generatori brojeva dati nekvalitetno mešanje.  

Veličina semena PRNG i najveća lista na kojoj se može doći do svake permutacije

zrna bitova	maksimalna dužina liste
0	1
1	2
3	3
5	4
7	5
10	6
13	7
16	8
22	10
24	10
32	12
48	16
64	20
128	34
160	40
226	52
256	57
512	98
1024	170
1600	245
19937	2080
44497	4199

Vidi još

• RC4
• Uzorkovanje iz rezervoara