View Issue Details
ID  Project  Category  View Status  Date Submitted  Last Update 

0036696  FPC  Packages  public  20200212 15:58  20200213 11:45 
Reporter  WayneSherman  Assigned To  
Priority  normal  Severity  minor  Reproducibility  always 
Status  new  Resolution  open  
Summary  0036696: TArrayUtils.RandomShuffle produces biased results  
Description  ../packages/fclstl/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:=size1 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  
Tags  No tags attached.  
Fixed in Revision  
FPCOldBugId  
FPCTarget  
Attached Files 


Also reference: https://forum.lazarus.freepascal.org/index.php/topic,36445.msg349000.html#msg349000 

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. 
Date Modified  Username  Field  Change 

20200212 15:58  WayneSherman  New Issue  
20200212 16:08  WayneSherman  Note Added: 0121052  
20200213 11:42  Thaddy de Koning  Note Added: 0121082  
20200213 11:45  Thaddy de Koning  Note Edited: 0121082  View Revisions 