Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What are the problem?

posted at

updated at

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

はじめに

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 }
  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() 関数をコレクションにしても面白いかもですね...って、"ホクホクのイモ" の時に書いとったわ!

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:

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
1
Help us understand the problem. What are the problem?