【Delphi】Fisher–Yates のシャッフル

はじめに

Fisher–Yates のシャッフルを Delphi で書いてみようと思います。

※ Delphi 10.4 Sydney を使っていますが、10.3 Rio でも大丈夫です。

コード

アルゴリズムは 箱からランダムで値を取り出して別の場所に置くことを繰り返す だけです。

• フィッシャー–イェーツのシャッフル (Wikipedia)

このシンプルなアルゴリズムに 「フィッシャー–イェーツのシャッフル (Fisher–Yates shuffle)」 という名前が付いている事を知ったのはそんなに昔ではありませんでした。ちょっとプログラムの経験がある人は名前は知らなくても、一度は同様の実装をした事があるんじゃないでしょうか？

ShuffledIndex() 関数

シャッフルされた Integer 配列を返す関数です。

function ShuffledIndex(const Count: Integer): TArray<Integer>;
begin
  SetLength(Result, Count);
  for var i := 0 to High(Result) do
    Result[i] := i;
  for var i := High(Result) downto 1 do
  begin
    var j := Random(Succ(i));
    var t := Result[j]; Result[j] := Result[i]; Result[i] := t;
  end;
end; { ShuffledIndex }

Delphi 7 や 2007 だと次のようになります。

uses
  Types;

function ShuffledIndex(const Count: Integer): TIntegerDynArray;
var
  i, j, t: Integer;
begin
  SetLength(Result, Count);
  for i := 0 to High(Result) do
    Result[i] := i;
  for i := High(Result) downto 1 do
  begin
    j := Random(Succ(i));
    t := Result[j]; Result[j] := Result[i]; Result[i] := t;
  end;
end; { ShuffledIndex }

1. パラメータ Count の数で Integer 型の動的配列 (結果) を初期化。
2. 配列の先頭から順に 0..Count-1 の数値を格納。
3. 配列をシャッフル。

この関数さえあればいかなる型の配列でもシャッフルできます。アルゴリズムは簡単なのでその都度書いてもいいのですが、一つ関数を書いておくと便利ですよね。

実行

次のような感じで使えます。例では String 型の配列をシャッフルしてコンソールに出力しています。

FisherYatesShuffle.dpr

program FisherYatesShuffle;
{$APPTYPE CONSOLE}

  function ShuffledIndex(const Count: Integer): TArray<Integer>;
    ...
  end; { ShuffledIndex }

begin
  Randomize;
  var a := ['ZERO', 'UNO', 'DUE', 'NANO', 'MICRO', 'PRO MINI', 'PRO MICRO', 'LEONARDO', 'MEGA2560'];
  for var i in ShuffledIndex(Length(a)) do
    Writeln(a[i]);
end.

Delphi 2007 ではこうなります。

FisherYatesShuffle.dpr

program FisherYatesShuffle;
{$APPTYPE CONSOLE}
uses
  Types;

var
  a: TStringDynArray;
  i: Integer;

  function ShuffledIndex(const Count: Integer): TIntegerDynArray;
    ...
  end; { ShuffledIndex }

begin
  Randomize;
  a := TStringDynArray.Create('ZERO', 'UNO', 'DUE', 'NANO', 'MICRO', 'PRO MINI', 'PRO MICRO', 'LEONARDO', 'MEGA2560');
  for i in ShuffledIndex(Length(a)) do
    Writeln(a[i]);
end.

Delphi 7 だとこうなります。

FisherYatesShuffle.dpr

program FisherYatesShuffle;

{$APPTYPE CONSOLE}

uses
  Types;

var
  a: TStringDynArray;
  i: Integer;
  ia: TIntegerDynArray;

  function ShuffledIndex(const Count: Integer): TIntegerDynArray;
    ...
  end;

begin
  Randomize;
  SetLength(a, 9);
  a[0] := 'ZERO';
  a[1] := 'UNO';
  a[2] := 'DUE';
  a[3] := 'NANO';
  a[4] := 'MICRO';
  a[5] := 'PRO MINI';
  a[6] := 'PRO MICRO';
  a[7] := 'LEONARDO';
  a[8] := 'MEGA2560';

  ia := ShuffledIndex(Length(a));
  for i := 0 to High(ia)  do
    Writeln(a[ia[i]]);
end.

おわりに

あまり必要性を感じませんが、ShuffledIndex() 関数をコレクションにしても面白いかもですね...って、"ホクホクのイモ" の時に書いとったわ！

• ホクホクのイモを Delphi で書いてみる (Qiita)

FisherYatesShuffle.dpr

program FisherYatesShuffle;
{$APPTYPE CONSOLE}

uses
  uPermutations;

begin
  Randomize;
  var a := ['ZERO', 'UNO', 'DUE', 'NANO', 'MICRO', 'PRO MINI', 'PRO MICRO', 'LEONARDO', 'MEGA2560'];
  for var i in Perm(Length(a)) do
    Writeln(a[i]);
end.

アラ、簡単。

See also:

• <6> 構造化型の概要と配列型 (標準 Pascal 範囲内での Delphi 入門) (Qiita)