TArrayUtils.RandomShuffle produces biased results
Original Reporter info from Mantis: WayneSherman
-
Reporter name:
Original Reporter info from Mantis: WayneSherman
- Reporter name:
Description:
../packages/fcl-stl/src/garrayutils.pp
RandomShuffle produces a biased result. It does not allow the possibility that a shuffled element will remain unchanged. In a truly random shuffle, the possibility exists that an element will remain the same value.
Current implementation:
class procedure TArrayUtils.RandomShuffle(Arr: TArr; size: SizeUInt);
var i,r:SizeUInt; temp:Tvalue;
begin
for i:=size-1 downto 1 do begin
r:=random(Int64(i));
temp:=Arr[r];
Arr[r]:=Arr[i];
Arr[i]:=temp;
end;
end;
Since random(Int64(i)) does not include i the line
r:=random(Int64(i));
should be changed to:
r:=random(Int64(i+1));
Additional information:
See:
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
j ← random integer such that 0 ≤ j ≤ i
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo's_algorithm
"In fact, as described below, it is quite easy to accidentally implement Sattolo's algorithm when the ordinary Fisher–Yates shuffle is intended. This will bias the results by causing the permutations to be picked from the smaller set of (n−1)! cycles of length N, instead of from the full set of all n! possible permutations. "
See also:
https://forum.lazarus.freepascal.org/index.php/topic,36445.msg349076.html#msg349076
Mantis conversion info:
- Mantis ID: 36696
- Build: Trunk