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|
|Product Version||Product Build||Trunk|
|Target Version||Fixed in Version|
|Summary||0036696: TArrayUtils.RandomShuffle produces biased results|
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.
class procedure TArrayUtils.RandomShuffle(Arr: TArr; size: SizeUInt);
var i,r:SizeUInt; temp:Tvalue;
for i:=size-1 downto 1 do begin
Since random(Int64(i)) does not include i the line
should be changed to:
j ← random integer such that 0 ≤ j ≤ i
"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. "
|Tags||No tags attached.|
|Fixed in Revision|
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.