Talk:Samples and permutations

From Free Pascal wiki
Jump to navigationJump to search

ANother example, not using 2 arrays, but only one, maybe:

type
  TIntegerDynArray= array of Integer;

{
  Returns an array of aSize random integers without duplicates ranging from
  aFrom (inclusive) to aTo (exclusive).
  - aFrom and aTo must be positive integers
  - aTo must be > aFrom
  - aSize must be <= aTo - aFrom
  - if either of these conditions is not met, an empty array will be returned.
}
function RandomArray(aFrom, aTo, aSize: Integer): TIntegerDynArray; overload;
var
  i, j, temp, Range: Integer;
begin
  Range := (aTo - aFrom);
  if (aFrom < 0) or (aFrom >= aTo) or (aSize > Range) then
    Exit(nil);
  SetLength(Result, Range);
  for i := Low(Result) to High(Result) do Result[i] := aFrom + i;
  // Use te Sattolo algorithm to shuffle the array
  // https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo.27s_algorithm
  i := Length(Result);
  while i > 0 do
  begin
    Dec(i);--~~~~
    j := Random(i);
    temp := Result[i];
    Result[i] := Result[j];
    Result[j] := temp;
  end;
  if (aSize <> Range) then
    SetLength(Result, aSize);
end;

function RandomArray(aFrom, aTo: Integer): TIntegerDynArray; inline; overload;
begin
  Result := RandomArray(aFrom, aTo, (aTo - aFrom));
end;

function RandomArray(Range: Integer): TIntegerDynArray; inline; overload;
begin
  Result := RandomArray(0, Range, Range);
end;

Thanks for providing this alternative example. I expect it to be more memory-efficient than my code. This may be especially beneficial in low-memory situations and embedded systems. It doesn't allow, however, for replacement. So, it may depend on the intended use and platform which algorithm to prefer. --Jwdietrich (talk) 14:18, 21 November 2020 (CET)
Thanks for clarifying that (replacement).--Bart (talk) 17:00, 21 November 2020 (CET)