[filmil]

Originalno napisao DejanVesic

U dva projekta sa sličnom tematikom sam radio sledeće:
(...)

rnd1 = NextRnd();
rnd2 = NextRnd();

for(j=0; j < 1,000,000; j++) 
{
    swap(a[rnd1],a[rnd2]);
    rnd1 = NextRnd();
    rnd2 = NextRnd();
}

На жалост, метод који си описао није добар, јер низ који се добија нема униформну расподелу(*).

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

Треће решење које ми пада на памет, које захтева константан простор и константно време за израчунавање, јесте генерисање неког хеша (МД5, СХА1) на основу (рецимо) монотоног системског сата (то је сат који се састоји од две компоненте: системског времена, и инкремента који се повећава за један сваки пут када се генерише један хеш. Згодно је за почетни инкремент узети излаз из /dev/random. Монотоно време је збир дотична два.)

Вероватноћа да се хешеви милион узастопних уноса сударе је занемарљиво мала (из праксе: још нисам наишао ни на једну), а расподела кључева треба да је униформна.

ф

(*) Доказ тврдње, за радознале: горе поменут алгоритам има 1е6^1e6 могућих исхода пермутовања. Пошто укупно има 1е6! пермутација од милион елемената (! = факторијел), што је број који је мањи од милион на милионити степен, то се свака од пермутација мора да понови много пута.

Ако је расподела униформна, онда се свака пермутација јавља једнак и цео број пута. Број понављања сваке пермутације је онда 1e6^1e6/1e6!, укупан број исхода подељен бројем различитих исхода.

Међутим, овај број не може да буде цео, на пример зато што је именилац дељив са 3, док бројилац није дељив са 3.

Закључак — пермутовање низа на горе описани начин не може да да униформну расподелу бројева, па ни униформну расподелу пермутација низа 0..1е6-1.