View Issue Details

IDProjectCategoryView StatusLast Update
0036696FPCPackagespublic2020-02-13 11:45
ReporterWayneShermanAssigned To 
PrioritynormalSeverityminorReproducibilityalways
Status newResolutionopen 
Product VersionProduct BuildTrunk 
Target VersionFixed in Version 
Summary0036696: TArrayUtils.RandomShuffle produces biased results
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 InformationSee:
  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
TagsNo tags attached.
Fixed in Revision
FPCOldBugId
FPCTarget
Attached Files

Activities

WayneSherman

2020-02-12 16:08

reporter   ~0121052

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

Thaddy de Koning

2020-02-13 11:42

reporter   ~0121082

Last edited: 2020-02-13 11:45

View 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.

Issue History

Date Modified Username Field Change
2020-02-12 15:58 WayneSherman New Issue
2020-02-12 16:08 WayneSherman Note Added: 0121052
2020-02-13 11:42 Thaddy de Koning Note Added: 0121082
2020-02-13 11:45 Thaddy de Koning Note Edited: 0121082 View Revisions