Защо е използван конкретния код за Random в цикъла?

Question

Защо е използван конкретния код за Random в цикъла
В задачата от компилатора, с размяната на думите от скороговорката, имаме:

rand = r.Next(0,i+1); // Взимаме произволно число

Това не е чак толкова произволно число, тъй като за i=0 ще е 0, за i=1 ще е 0 или 1 и така до последното i (0 до i). По този начин, според мен, се постига следните два ефекта: 
* всяка дума може да бъде заменена само с предходна; 
* на последните думи се дават твърде малко възможности за размяна.

За да се даде еднакъв "шанс" на всички думи да се разместват, в т.ч. и с думи след тях, не е ли по-добре кода да бъде:

rand = r.Next(0,a.Length);

Ако е заложен допълнителен (или различен) мотив в оригиналния код, моля да разкажете с няколко думи. 
Благодаря!

Веселин · Accepted Answer

Напълно си прав, алгоритъма за разместване (shuffle) в упражнението е - 'biased'. Тоест - няма да даде равен шанс на всички думи.  Написал съм го така, защото съм бързал :) ,но сега ще поправя грешката.

Ако искаш алгоритъм да е 'unbiased'. То може да изпозлваш Fisher-Yates алгоритъм за разместване. 
( Схематично написан, не е C#, но пък се разбира лесно)

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

или обратното (което има същия ефект)

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that 0 ≤ j < n-i
     exchange a[i] and a[i+j]

Ако го пуснеш например 10000 пъти и сравниш резултатите, то би трябвало всяка дума да има равен шанс с другите да попадне на което и да е място.

Според мен с предложението което ти даваш

rand = r.Next(0,a.Length);

Ще получиш по-добри резултати от алгоритъма в упражнението, но пак няма да е 'unbiased'.
Ако пуснеш цикъла достатъчно дълго да размества, ще подобряваш шансовете, но пък ще увеличиш времето за изчисление, докато Fisher-Yates, ще прави същото, но за много по-малко време.

Иван Георгиев Даскалов · Answer

Извинявай за супер късния коментар, но благодаря за отговора ти.

Защо е използван конкретния код за Random в цикъла?

Вашият отговор