はじめに
Fisher–Yates のシャッフルを Delphi で書いてみようと思います。
※ Delphi 10.4 Sydney を使っていますが、10.3 Rio でも大丈夫です。
コード
アルゴリズムは 箱からランダムで値を取り出して別の場所に置くことを繰り返す だけです。
このシンプルなアルゴリズムに 「フィッシャー–イェーツのシャッフル (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 }
- パラメータ Count の数で Integer 型の動的配列 (結果) を初期化。
- 配列の先頭から順に
0..Count-1の数値を格納。 - 配列をシャッフル。
この関数さえあればいかなる型の配列でもシャッフルできます。アルゴリズムは簡単なのでその都度書いてもいいのですが、一つ関数を書いておくと便利ですよね。
実行
次のような感じで使えます。例では 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() 関数をコレクションにしても面白いかもですね...って、"ホクホクのイモ" の時に書いとったわ！
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: