#### View Issue Details

ID Project Category View Status Date Submitted Last Update 0036696 FPC Packages public 2020-02-12 15:58 2020-02-13 11:45 WayneSherman normal minor always new open 0036696: TArrayUtils.RandomShuffle produces biased results ../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)); 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 No tags attached. Attached Files

#### Activities

 2020-02-12 16:08 reporter   ~0121052 Also reference: https://forum.lazarus.freepascal.org/index.php/topic,36445.msg349000.html#msg349000 2020-02-13 11:42 reporter   ~0121082 Last edited: 2020-02-13 11:45View 2 revisions I believe that implementation to be correct for its intended purpose. One just has to document what kind of shuffle is implemented. The fact that all elements have a different position is intentional.