Фишер–Јетсово мешање

Фишер–Јетсово мешање је алгоритам који генерише насумичне пермутације коначног низа, упрошћено, тај алгоритам меша низ. Ефективно, алгоритам ставља све елементе у шешир; континуирано одређује следећи елемент тако што насумично извлачи елемент из шешира док не остане ниједан. Тај алгоритам производи непристрасне пермутације: свака пермутација је подједнако вероватна. Модерна верзија овог алгоритма је ефикасна: време које му је потребно је пропорционално броју елемената који се мешају и меша их у место.

Фишер–Јетсово мешање је названо по Роналду Фишеру и Френку Јетсу који су га први описали а такође је познато и као Кнут мешање по Доналду Кнуту. Варијација Фишер–Јетсово мешање, позната као Сатолов алгоритам, се може користити за генерисање насумичних цикличних пермутација дужине n уместо насумичних пермутација.

Оригинална Фишер-Jeтсова метода

Фишер–Јетсово мешање у својој оригиналној форми су 1938. описали Роналд Фишер и Френк Јетс у својој књизи Статистичке табеле за биолошка, пољопривредна и медицинска истраживања.^[1] Њихов опис алгоритма је користио оловку и папир; табела са насумичним бројевима је омогућавала насумичност. Основни метод за генерисање насумичних пермутација бројева од 1 до N следи:

Напиши бројеве од 1 до N.
Изабери насумични број k.
Рачунајући са доњег краја, прецртај редни број k.
Понављајте од корака 2 док се не избришу сви бројеви.
Низ бројева записан у кораку 3 је сада насумична пермутација оригиналних бројева.

Под условом да су насумични бројеви изабрани у кораку 2 изнад заиста насумични и непристрасни, таква ће бити и резултујућа пермутација.Фишер и Јетс су пажљиво описали како да се добију такви насумични бројеви у било ком жељеном распону из приложених табела на начин који избегава икакву пристрасност. Такође су предложили могућност коришћења простије методе-одабир насумичних бројева од 1 до N уз одстрањивање дуплих бројева - како би се генерисала прва половина пермутације и примењивање сложенијег алгоритма само на другу половину где би одабир дуплог броја постао фрустрирајуће чест.

Модерни алгоритам

Модерну верзију Фишер–Јетсово мешања, дизајнирану за употребу на рачунарима, је 1964. ^[2]увео Ричард Дурстенфелд, а популарном је учинио Доналд Е. Кнут у Уметност рачунарског програмирања као „Алгоритам П (мешање)“. ^[3] Ни Дурестенфелдови чланци ни Кнутово прво издање Уметност рачунарског програмирања нису одали признање Фишер-у и Јетсу за њихов рад; можда нису били тога свесни. Следећа издања Кнутовог Уметност рачунарског програмирања Фишеров и Јетсов допринос.^[4]

Алгоритам који је описао Дурстенфелд се мало разликује од онога који си дали Фишер и Јетс, али је та разлика значајна. Док би изворна рачунарска имплементација Фишер-Јетс методе траћила време бројећи преостале бројеве у кораку 3 изнад, Дурстенфелдово решење је да се помере прецртани бројеви на крај листе при чему мењају места са последњим непрецртаним бројем при свакој итерацији. Ово смањује субекспоненцијално време алгоритма на ${\mathcal {O}}(n)$ , у односу на ${\mathcal {O}}(n^{2})$ из оригиналне наивне имплементације.^[5] Ова промена даје следећи алгоритам (за низ заснован на нули).

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

Еквивалентна верзија која меша низ у супротном смеру (од најнижег индекса до највишег) је:

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

Примери

Метода оловка и папир

Као пример, пермутоваћемо бројеве од 1 до 8 користећи оригиналну Фишер–Јетсово методу. Почећемо исписивањем бројева на папиру:

Опсег	Извучени	Прецртани	Резултат
		1 2 3 4 5 6 7 8

Сада извлачимо насумичан број к од 1 до 8 – нека то буде 3 – и прецртамо к-ти број на папиру а запишемо га као резултат:

Опсег	Извучени	Прецртани	Резултат
1–8	3	1 2 3 4 5 6 7 8	3

Сада бирамо следећи насумични број, овог пута од 1 до 7: изгледа да је то 4. Сада прецртамо четврти бројкоји још није већ прецртану делу табеле са прецртаним бројевима – то је број 5 – и додамо га резултату:

Опсег	Извучени	Прецртани	Резултат
1–7	4	1 2 3 4 5 6 7 8	3 5

Сада бирамо следећи насумични број од 1 до 6 а затим од 1 до 5 и тако даље уз понављање претходног процеса прецртавања:

Опсег	Извучени	Прецртани	Резултат
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

Moдерна метода

Сада ћемо урадити исту ствар користећи Дурстенфелдову верзију алгоритма: овог пута, уместо прецртавања изабраних бројева, а затим копирања, ми ћемо из заменити са последњим бројем који још увек није изабран. Почећемо писањем бројева од 1 до 8 као пре:

Опсег	Извучени	Прецртани	Резултат
		1 2 3 4 5 6 7 8

За наше прво извлачење добијамо насумични број од 1 до 8: овог пута то је 6. Замењујемо шести и седми број на листи:

Опсег	Извучени	Прецртани	Резултат
1–8	6	1 2 3 4 5 8 7	6

Следећи насумични број извлачимо у опсегу 1 до 7, и изгледа да ће тај број бити 2. Тако да, замењујемо други и седми број и настављамо:

Опсег	Извучени	Прецртани	Резултат
1–7	2	1 7 3 4 5 8	2 6

Следећи број који извлачимо је из опсега од 1 до 6 и то је 6. То значи да остављамо шести број на листи (који је, после замене изнад, број 8) на исто место и само прелазимо на следећи корак. Поново, настављамо на исти начин док се пермутација не заврши:

Опсег	Извучени	Прецртани	Резултат
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

И сада се више ништа не може урадити тако да је резултујућа пермутација 7 5 4 3 1 8 2 6.

Варијације

Наопаки алгоритам

Фишер–Јетсово мешање , како га имплементира Дурстенфелд, је мешање у место. То јест, са унапред иницијализованим низом он меша елементе тог низа у место, а не ствара мешану копију тог низа. Ово може бити предност ако је низ који би требало мешати велики.

Како би се симултано иницијализовао и мешао низ може се постићи већа ефикасност коришћењем наопаке верзије мешања. У овој верзији се сукцесивно ставља елемент број i на насумичну позицију међу првим i позицијама у низу након померања елемента који је претходно заузимао ту позицију до позиције i. У случају да је насумична позиција број i, ово " померање" (на исто место) укључује неиницијализовану вредност, али то није важно, јер се преко те вредности онда одмах преписује друга. Није потребна засебна иницијализација и не ради се замена. У уобичајеним случајевима где се извор дефинише неком простом функцијом као што су цели бројеви од 0 до n − 1, извор се може једноставно заменити функцијом јер се извор никад не мења током извршавања.

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

Наопако мешање може изгледати исправно кроз индукцију. Под претпоставком савршеног генератора насумичних бројева, сваки од n! различитих низова насумичних бројева који се могу добити насумичним позивањем произвешће другачије пермутације вредности, тако да се оне добијају само једном. Услов који проверава да ли ј ≠ i се може занемарити у језицима који немају проблема при оцењивању неиницијализованих вредности низа. Ово елиминише n условне гране по цену H_n ≈ ln n + γ редундантних задатака.

Друга предност ове технике је да n, број елемената у извору, не мора да се зна унапред; само морамо да имамо могућност да детектујемо крај изворних података када се стигне до тог краја. Испод, низ а се гради итеративно почевши од празнине, а а дужина представља тренутни број видљивих елемената.

Да бисте иницијализовали празан низ а случајно премешаном копијом извора чија дужина није позната:
  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

Сатоло алгоритам

Сличан алгоритам је објавила Сандра Саттоло 1986. за генерисање једнако дистрибуисаних циклуса (максималне) дужине n. ^[6]^[7]Једина разлика између Дустенфелд и Сатоло алгоритма је да се у овом другом алгоритму, у кораку 2 изнад, насумични број ј инклузивно бира из опсега између 1 и i-1 (пре него између 1 и i). Ова једноставна промена мења алгоритам тако да се резултујућа пермутација увек састоји од једног низа.

Заправо, као што је испод описано, веома је лако да се 'нехотице' имплементира Сатоло алгоритам када се планира обично Фисхер-Yатес мешање. Ово ће произвести пристрасне резултате тако што проузрокује бирање пермутација из мањег скупа (n−1)! циклуса дужине N, уместо из целог скупа свих n! могућих пермутација.

Чињеница да Саттоло алгоритам увек производи циклус дужине n може бити приказана индукцијом. Индукцијом претпоставимо да после почетне итерације петље, преостале итерације пермутују прве n−1 елементе према циклусу дужине n−1 (те преостале итерације су само Саттоло алгоритам примењен на те прве n−1 елементе). Ово значи да се праћењем почетног елемента до његове нове позиције п, а затим елемента оригинално на позицији p до његове нове позиције и тако даље само враћамо на почетну позицију након посећивања свих других позиција. Претпоставимо да је почетна итерација заменила коначни елемент са оним на позицији к (која није крања) и да је произилазећа пермутација првих n−1 елемената и затим га померила на позицију l; ми поредимо пермутацију p свих n елемената са том преосталом пермутацијом σ првих n−1 елемената. Праћењем сукцесивних позиција као што је управо поменуто, види се да не постоји разлика између p и σ док се не стигне до позиције к. Али онда, под π елемент оригинално на позицији к се помера на крајњу позицију а не на позицију l, а елемент оригинално на крајњој позицији се помера на позицију л. Одатле, низ позиција за p опет прати низ за σ и све позиције ће опет бити посећене пре враћања на почетну позицију, као што се захтева.

Што се тиче једнаке вероватноће пермутација довољно је приметити да модификовани алгоритам укључује (n−1)! различитих могућих низова насумично генерисаних бројева од којих сваки јасно производи различите пермутације и сваки се одвија - под претпоставком да је извор насумичног броја непристрасан - са подједнаком вероватноћом. (n−1)! различите пермутације које су на овај начин добијене прецизно исцрпљују скуп циклуса дужине n: сваки такав циклус има јединствену нотацију циклуса где је вредност n на коначној позицији, што омогућава да (n−1)! пермутација преосталих вредности испуни друге позиције нотације циклуса.

Пример имплементације Сатоло алгоритма у Пајтону је:

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]

Поређење са другим алгоритмима

Асимптотична комплексност времена и простора при Фишер–Јетсовом мешању је оптимална. У комбинацији са непристрасним и високо квалитетним извором насумичних бројева такође је загарантовано генерисање непристрасних резултата. У поређењу са неким другим решењима такође има предност да се, ако је потребан само део резултујуће пермутације, може зауставити у сред процеса или се чак може зауставити и поновно покретати у више наврата при чему се пермутације генерише постепено по потреби.

Наивна метода

Наивна метода замене сваког елемента са другим елементом који је насумично одабран из свих елемената је пристрасна и у основни неисправна. ^[8]Различите пермутације ће имати различите вероватноће генерисања за сваки $n>2$ , јер број различитих пермутација, $n!$ , неједнако дели број насумичних исхода алгоритма, $n^{n}$ . Нарочито, према Бертрандовом постулату биће бар један прост број између $n/2$ и $n$ , и овај број ће делити $n!$ али неће делити $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]

Сорти

Алтернативна метода задаје насумични број сваком елементу скупа који треба мешати а затим сортира скуп према задатим бројевима. Метода сортирања има исте асимптотичке комплексности као Фишер–Јетс: иако је генерално сортирање О(n log n), бројеви се ефикасно сортирају коришћењем радикс сортирања у О(n) времену. Као Фишер–Јетсово мешање ова метода сортирања даје непристрасне резултате. Ипак, мора се водити брига да се задати бројеви никад не дуплирају јер алгоритми сортирања типично не ређају елементе насумично у случају изједначености. Поред тога, ова метода захтева асимптотично већи простор: О(n) додатни простор за складиштење за насумичне бројеве, у поређењу са О(1) простором за Фишер–Јетсово мешање.^[9] Коначно, приметно је да метода мешања има једноставну паралелну имплементацију за разлику од Фишер–Јетсово мешањa, које је секвентно.

Варијација методе одозго је да се меша листа тако што се сортира са функцијом поређења која даје насумичне вредности. ^[10]^[11]Ова варијација се користи у језицима који подржавају сортирање са функцијама поређења које корисници одређују. Међутим, ово је веома лоша метода: врло је вероватно да се дође до веома неуједначених дистрибуција, што додатно увелико зависи од алгоритма за сортирање који се користи. На пример, претпоставимо да се qуицксорт користи као сортирајући алгоритам, са фиксним елементом изабраним као први пивотни елемент. Алгоритам почиње поређењем пивотног са свим осталим елементима како би их поделио на оне мање и оне веће од њега, а релативна величина тих група одредиће коначно место за пивотни елемент. За уједначено дистрибуисану насумичну пермутацију свака могућа коначна позиција би требало да буде подједнако вероватна за пивотни елемент, али ако свако од почетних поређења даје 'мање' или 'веће' са једнаком вероватноћом онда ће та позиција имати биномиалну расподела за p = 1/2, што даје позицију близу средине низа са много већом вероватноћом него позиције близу крајева. Насумичне функције упоређивања које се примењују на друге методе сортирања као што су сортирање спајањем могу дати резултате који изгледају уједначеније, али и нису баш јер спајање два низа тако што се поновно бира један од њих са једнаком вероватноћом (док се избор не изнуди исцрпљивањем једног низа) не даје резултате са уједначеном дистрибуцијом; уместо тога вероватноћа да се одабере низ би требало да буде пропорционална броју елемената који су преостали у низу. Заправно ниједна метода која користи само двосмерне насумичне догађаје са једнаком вероватноћом (бацање новчића), а која се понавља ограничен број пута, не може да оствари пермутације низа (са више од два елемента) са уједначеном дистрибуцијом јер свака линија извршења ће за вероватноћу имати рационални број са степеном двојке као деноминатор, док потребна вероватноћа 1/n! за сваку могућу пермутацију није у тој форми.

У принципу ова метода мешања може чак и да резултира отказивањем програма попут бескрајних петљи или крсења приступа, јер исправност сортирајућег алгоритма може да зависи од карактеристика односа редоследа (попут транзитивности) које поређење које даје насумичне вредности сигурно неће имати. Док се оваква врста понашања не сме догађати у сортирајућим рутинама које никад не врше поређења чији се исходи са сигурношћу могу предвидети (засновано на претходним поређењима), могу да постоје валидни разлози за намерно упоређивање на тај начин. На пример чињеница да би сваки елемент требало да се пореди као себи једнак дозвољава њихово коришћење као сигналну вредност због ефикасности, па ако је то случај насумична функција поређења би покварила сортирајући алгоритам.

Mогући извори пристрасности

Мора се водити рачуна када се имплементира Фишер–Јетсово мешање и при имплементацији самог алгоритма и при генерисању насумичних бројева на којима се он гради. У супротном, резултати могу показати приметну пристрасност. Један број уобичајених извора пристрасности је дат испод.

Грешке у имплементацији

Уобичајена грешка када се имплементира Фишер–Јетсово мешање је да се бирају насумични бројеви из погрешног опсега. Такав мањкави алгоритам може изгледати нормално али неће произвести сваку могућу пермутацију са једнаком вероватноћом, а неке пермутације можда неће уопште произвести. На пример, уобичајена грешка за један била би одабир индекса ј уноса за замену у примеру изнад да увек буде мањи од индекса и уноса са којим се замењује. Ово мења Фишер–Јетсово мешање у Сатоло алгоритам што производи само пермутације које се састоје од једног циклуса који укључује све елементе: нарочито, са овом модификацијом, ниједан елемент низа никад не може да заврши на својој почетној позицији.

Слично, стални одабир ј из целог опсега валидних индекса низова са сваком итерацијом такође производи пристрасни резултат мада је то мање уочљиво. Ово се види из чињенице да се оваквом применом добија nⁿ различитих могућих низова замена где постоји само n! могућих пермутација низа n елемената. Пошто nⁿ никад није једнако дељив са n! када n > 2 (јер је овај други дељив са n−1, који нема заједничке просте бројеве са n), неке пермутације морају да происходе из више nⁿ низова замена од других. Као конкретан пример ове пристрасности приметимо дистрибуцију могућих исхода мешања низа са три елемента [1, 2, 3]. Постоји шест могућих пермутација овог низа (3!=6), али алгоритам производи 27 могућих мешања (3³ = 27). У овом случају, сваки [1, 2, 3], [3, 1, 2] и [3, 2, 1] резултирају са четири од могућих 27 мешања, док се свака од преостале три пермутације јавља у 5 од 27 мешања.

Матрица са десне стране показује вероватноћу сваког елемента на листи дужине 7 који завршава на било којој другој позицији. Приметите да за већину елемената, завршавање на оригиналној позицији (главна дијагонала матрице) има најмању вероватноћу, а померање за једно место уназад има највећу вероватноћу.

Moдуло пристрасности

Фишер–Јетсово мешање укључује одабир дискретних униформних расподели целих бројева из различитих опсега. Већина генерисаних случајних бројева, ипак - било правих или псеудо-насумичних - ће само директно дати бројеве у одређеном опсегу од 0 до RAND_MAX, а у неким библиотекама, RAND_MAX може бити низак и до 32767. ^[12]Једноставан и најчешће коришћен начин да се такви бројеви угурају у жељени опсег је да се примени модуло оператор; то јест, да се поделе по величини опсега и да се узме остатак. Међутим, потреба у Фишер–Јетсово мешању да се генеришу насумични бројеви у сваком оспегу од 0–1 до 0–n прилично гарантује да неки од ових оспега неће једнако поделити природни оспег генератора насумичних бројева. Тако, остаци неће увек бити уједначено дистрибуисани и, још горе, пристрасност ће систематски бити на страни малих остатака.

На пример, претпоставимо да ваш извор насумичних бројева даје бројеве од 0 до 99 (као што је то био случај за Фисхер-ове и Yатес-ове оригиналне табеле), и да ви желите да добијете непристрасни насумични број од 0 до 15. Ако једноставно поделите бројеве бројем 16 и узмете остатак видећете да се бројеви 0–3 јављају око 17% чешће од других. То је зато што 16 не дели 100 једнако: највећи производ броја 16 мањи или једнак броју 100 је 6x16=96, а бројеви у несвршеном низу 96–99 изазивају пристрасност. Најједноставнији начин да се поправи проблем је да се одбаце ти бројеви пре узимања остатка и да се настави са покушајима док се не појави број у одговарајућем опсегу. Док би ово у принципу, у најгорем случају, могло да траје заувек, очекивани број покушаја ће увек бити мањи од једног.

Проблем у вези са овим се јавља са имплементацијама које прво генеришу насумични број са покретним зарезом - обично у опсегу [0,1), а затим га множе величином жељеног опсега и заокруже га. Овде је проблем то што бројеви са покретним зарезом, колико год опрезно генерисани, увек имају само ограничену прецизност. Ово значи да постоји само ограничени број могућих вредности са покретним зарезом у било ком опсегу, а ако је опсег подељен на одређени број сегмената који не дели овај број једнако, неки сегменти ће завршити са вероватнијим вредностима него други. Док резултујућа пристрасност неће показати исту систематску падајућу тенденцију као у претходном случају, она ће и даље бити ту.

Псеудо-насумични генератори

Додатни проблем се јавља када се Фишер–Јетсово мешање користи са псеудо-насумичним генератором бројева или PRNG: пошто је низ бројева које такав генератор избаци потпуно одређен својим интерним стањем на почетку низа мешање које врши такав генератор једноставно не може да произведе више различитих пермутација него генератор који има различита могућа стања.^[13] Чак и када број могућих стања превазилази број пермутација неправилна природа мапирања из низова бројева на пермутације значи да ће се неке пермутације јављати чешће него друге. Тако, да би се смањила пристрасност, број стања PRNG-а би требало да превазилази број пермутација за најмање неколико редова величине.

На пример, уграђени псеудо-насумични генератор бројева у многим програмским језицима и/или библиотеке могу имати само 32 бита интерног стања, што значи да могу да произведу 2³² различитих низова бројева. Ако се такав генератор користи да се меша шпил од 52 карте, он може само да произведе врло мали део 52! ≈ 2^225.6 могућих пермутација. Могуће је да генератор са мање од 226 битова интерног стања произведе све могуће пермутације шпила од 52 карте.

Ниједан псеудо-насумични генератор бројева не може да произведе више различитих низова, почевши од тачке иницијализације, од броја различитих почетних вредности. Тако, генератор који има 1024 бита интерног стања али који се иницијализује са 32-бит почетним вредностима и даље може да произведе само 2³² различитих пермутација одмах након иницијализације. Може да произведе више пермутација ако се генератор испробава много више пута пре његовог коришћења за генерисање пермутација, али је ово веома неефикасан начин повећања насумичности: под претпоставком да се може средити да неко искористи генератор насумичан број пута до милијарде, на пример, да поједноставимо, 2³⁰ пута између иницијализације и генерисање пермутација, онда је број могућих пермутација и даље само 2⁶².

Додатни проблем се јавља када се користи прост линеарни конгруентни PRNG са методом дељења и узимања остатка за смањење опсега која је описана изнад. Овде је проблем то што су битови нижег реда линеарног конгруентног PRNG-а са модуло 2^е мање насумични од оних вишег реда:^[4] сами ниски n битови генератора имају период од скоро 2ⁿ. Када је делилац степен двојке, узимање остатка у суштини значи одбацивање битова вишег реда, тако да се добије знатно мање насумична вредност. Другачија правила се примењују ако линеарни конгруентни генератор има модуло са простим бројем, али такви генератори су ретки. Ово је пример општег правила да ће неквалитетни генератори насумичних бројева или псеудо-насумични генератори бројева дати неквалитетно мешање.

Величина семена PRNG и највећа листа на којој се може доћи до сваке пермутације
зрна битова	максимална дужина листе
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

Види још

Референце

^ Fisher, Ronald A, Yates, Frank (1948). Statistical tables for biological, agricultural and medical research (3rd ed.). Londo. London.
^ Durstenfeld, R (јул 1964). "Algorithm 235: Random permutation". Communications of the ACM.
^ Knuth, Donald E (1969). Seminumerical algorithms. The Art of Computer Programming. Addison–Wesley.
^ ^а ^б Knuth (1998). minumerical algorithms. The Art of Computer Programming. 2 (3rd ed.). Boston.
^ Black, Paul E. (19. 12. 2015). „Dictionary of Algorithms and Data Structures.”. Приступљено 19. 01. 2021.
^ Sattolo, Sandra (1986-05-30). "An algorithm to generate a random cyclic permutation".
^ Wilson, Mark (2002—2004). „Overview of Sattolo’s Algorithm” (PDF). Приступљено 15. 01. 2021.
^ Atwood, Jeff (2007-12-07). „The Danger of Naïveté”. Приступљено 15. 01. 2021.
^ Kiselyov, Oleg. „Provably perfect shuffle algorithms”. Приступљено 15. 01. 2021.
^ „A simple shuffle that proved not so simple after all”. 19. 06. 2007.
^ „Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot”. 27. 02. 2010. Приступљено 15. 01. 2021.
^ „ISO C Random Number Functions”. Приступљено 15. 01. 2021.
^ J¨org, Arndt (30. 10. 2009). „Generating Random Permutations” (PDF). Приступљено 15. 01. 2021.

[1] Fisher, Ronald A, Yates, Frank (1948). Statistical tables for biological, agricultural and medical research (3rd ed.). Londo. London.

[2] Durstenfeld, R (јул 1964). "Algorithm 235: Random permutation". Communications of the ACM.

[3] Knuth, Donald E (1969). Seminumerical algorithms. The Art of Computer Programming. Addison–Wesley.

[:0-4] а ^б Knuth (1998). minumerical algorithms. The Art of Computer Programming. 2 (3rd ed.). Boston.

[5] Black, Paul E. (19. 12. 2015). „Dictionary of Algorithms and Data Structures.”. Приступљено 19. 01. 2021.

[6] Sattolo, Sandra (1986-05-30). "An algorithm to generate a random cyclic permutation".

[7] Wilson, Mark (2002—2004). „Overview of Sattolo’s Algorithm” (PDF). Приступљено 15. 01. 2021.

[8] Atwood, Jeff (2007-12-07). „The Danger of Naïveté”. Приступљено 15. 01. 2021.

[9] Kiselyov, Oleg. „Provably perfect shuffle algorithms”. Приступљено 15. 01. 2021.

[10] „A simple shuffle that proved not so simple after all”. 19. 06. 2007.

[11] „Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot”. 27. 02. 2010. Приступљено 15. 01. 2021.

[12] „ISO C Random Number Functions”. Приступљено 15. 01. 2021.

[13] J¨org, Arndt (30. 10. 2009). „Generating Random Permutations” (PDF). Приступљено 15. 01. 2021.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]