重複のない乱数を生成（配列をシャッフル）するには？［C#／VB］：.NET TIPS

生成するたびに、その値が異なるような乱数を得る方法の中から、ダステンフェルドのアルゴリズムを使った方法と、もっと簡単だが速度面では不利な方法を紹介する。

[山本康彦，BluewaterSoft／Microsoft MVP for Windows Development]

連載目次

　重複のない乱数とは、例えば乱数を2つ生成したときに必ず異なる値が得られるということだ。そのようなアルゴリズムには生成され得る乱数が有限個に限定されるものとされないものとが考えられるが、本稿では限定した場合を扱う。例えば、1から10の整数の中から乱数を3つ生成するような場合である（生成され得る乱数は10個）。あるいは、トランプを使ったカードゲームでシャッフルするというのは、1から52（ジョーカーを含めるなら53）までの整数の範囲で重複しない乱数を52回（あるいは53回）生成することだと考えられるので、本稿のロジックで扱える。

　2通りの方法を紹介するので、特定の方法をすぐに知りたいという方は以下のリンクを活用してほしい。

• ダステンフェルドのアルゴリズム
• 分かりやすいロジック

　なお、ダステンフェルドのアルゴリズムは.NET Frameworkのバージョンによらず利用できるが、本稿に掲載したサンプルコードをそのまま試すにはVisual Studio 2015以降が必要である。

ダステンフェルドのアルゴリズム

　ダステンフェルドのアルゴリズムは、フィッシャー／イェーツのアルゴリズムを改良して1964年に公表されたものだ（Wikipedia参照）。ダステンフェルドのアルゴリズムを使って指定した整数の範囲で重複しない乱数を生成するメソッドは、次のコードのようになる。

static void Swap(ref int m, ref int n)
{
  int work = m;
  m = n;
  n = work;
}

static IEnumerable<int> GetUniqRandomNumbers(int rangeBegin, int rangeEnd, int count)
{
  // 指定された範囲の整数を格納できる配列を用意する
  int[] work = new int[rangeEnd - rangeBegin + 1];

  // 配列を初期化する
  for (int n = rangeBegin, i = 0; n <= rangeEnd; n++, i++)
    work[i] = n;

  // ランダムに取り出しては先頭から順に置いていく（count回繰り返す）
  var rnd = new Random();
  for (int resultPos = 0; resultPos < count; resultPos++)
  {
    // （resultPosを含めて）resultPosの後ろからランダムに1つ選ぶ
    int nextResultPos = rnd.Next(resultPos, work.Length);

    // nextResultPosの値をresultPosと入れ替える
    Swap(ref work[resultPos], ref work[nextResultPos]);
  }

  return work.Take(count); // workの先頭からcount個を返す
}

Sub Swap(ByRef m As Integer, ByRef n As Integer)
  Dim work As Integer = m
  m = n
  n = work
End Sub

Function GetUniqRandomNumbers(rangeBegin As Integer, rangeEnd As Integer, count As Integer) As IEnumerable(Of Integer)
  ' 指定された範囲の整数を格納できる配列を用意する
  Dim work(rangeEnd - rangeBegin) As Integer

  ' 配列を初期化する
  Dim i As Integer = 0
  For n As Integer = rangeBegin To rangeEnd
    work(i) = n
    i += 1
  Next

  ' ランダムに取り出しては先頭から順に置いていく（count回繰り返す）
  Dim rnd = New Random()
  For resultPos As Integer = 0 To count - 1
    ' （resultPosを含めて）resultPosの後ろからランダムに1つ選ぶ
    Dim nextResultPos As Integer = rnd.Next(resultPos, work.Length)

    ' nextResultPosの値をresultPosと入れ替える
    Swap(work(resultPos), work(nextResultPos))
  Next

  Return work.Take(count) ' workの先頭からcount個を返す

End Function

ダステンフェルドのアルゴリズムを使って重複しない乱数を生成するメソッド（上：C#、下：VB）
rangeBeginからrangeEndまでの範囲の整数から、重複しない乱数をcount個だけ生成する。ガード句を省略しているため、rangeBeginより小さいrangeEndを指定したり、範囲よりも大きいcountを指定したりすると例外を起こすので、注意してほしい。

　ダステンフェルドのアルゴリズムは、配列中のランダムな位置を選び、その値を先頭から（あるいは、末尾から）再配置していくというものだ（Wikipedia日本語版では末尾から配置していく方法だけが記載されているが、上のコードは先頭から配置していく方法だ）。配列を全て並べ替える必要がないときは（例えば1から10の範囲で3個だけ生成するときなど）、必要な数が（先頭または末尾に）集まった時点で打ち切ればよい。上のコードでは、ループ回数をcount回に制限している。

　なお、Randomクラス（System名前空間）はインスタンスを作るたびに異なる乱数系列を発生するようになっている。それは望ましい性質なのだが、デバッグ時には毎回同じ系列の乱数を生成してほしいこともある。そのようなときには、乱数のシードとして固定値を渡すようにするとよい（次のコード）。Randomクラスの詳細や、より偏りの少ない乱数を得る方法については、「.NET TIPS：乱数を生成するには？」を参照していただきたい。

#if DEBUG
  var rnd = new Random(0); // デバッグでは、毎回同じ乱数列を生成させる
#else
  var rnd = new Random();
#endif

#If DEBUG Then
  Dim rnd = New Random(0) ' デバッグでは、毎回同じ乱数列を生成させる
#Else
  Dim rnd = New Random()
#End If

デバッグ時には同じ系列の乱数を生成させるようにする例（上：C#、下：VB）

　上に掲載したダステンフェルドのアルゴリズムを使ったメソッドを実際に呼び出すコードは次のようになる。

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
  ……省略（前述のメソッド）……

  static void WriteNumbers(IEnumerable<int> numbers)
    => WriteLine(string.Join(", ", numbers));

  static void Main(string[] args)
  {
    WriteLine("1〜10の整数から3個");
    WriteNumbers(GetUniqRandomNumbers(1, 10, 3));
    // 出力例： 8, 9, 2

    WriteLine("-5〜5の整数から11個");
    WriteNumbers(GetUniqRandomNumbers(-5, 5, 11));
    // 出力例： 2, 4, 3, -5, 0, -3, 5, -1, 1, -4, -2

    WriteLine("1〜52の整数から10個");
    WriteNumbers(GetUniqRandomNumbers(1, 52, 10));
    // 出力例： 38, 43, 41, 31, 14, 32, 48, 27, 52, 21

#if DEBUG
    ReadKey();
#endif
  }
}

Imports System.Console

Module Module1
  ……省略（前述のメソッド）……

  Sub WriteNumbers(numbers As IEnumerable(Of Integer))
    WriteLine(String.Join(", ", numbers))
  End Sub

  Sub Main()
    WriteLine("1〜10の整数から3個")
    WriteNumbers(GetUniqRandomNumbers(1, 10, 3))
    ' 出力例： 8, 9, 2

    WriteLine("-5〜5の整数から11個")
    WriteNumbers(GetUniqRandomNumbers(-5, 5, 11))
    ' 出力例： 2, 4, 3, -5, 0, -3, 5, -1, 1, -4, -2

    WriteLine("1〜52の整数から10個")
    WriteNumbers(GetUniqRandomNumbers(1, 52, 10))
    ' 出力例： 38, 43, 41, 31, 14, 32, 48, 27, 52, 21

#If DEBUG Then
    ReadKey()
#End If
  End Sub
End Module

ダステンフェルドのアルゴリズムを呼び出すコンソールアプリの例（上：C#、下：VB）

　なお、ここでは整数を扱ったが、どんなオブジェクトでも構わない。例えば、トランプのカードを表すオブジェクトを配列に入れておけば、ランダムにシャッフルされたカードオブジェクトのコレクションが得られるというわけだ。

分かりやすいロジック

　ダステンフェルドのアルゴリズムはちょっと難解なので、分かりやすいロジックも紹介しておこう。処理速度は遅いが、実用上はこれでも十分なことが多いだろう。

　重複しないようにするには、1回取り出した値を取り除いてしまえばよい。指定された範囲の整数を格納したコレクションを作っておき、そこからランダムに1つ選んで値を取り出すとともにその値をコレクションから削除していけばよいのだ（次のコード）。

static IEnumerable<int> GetUniqRandomNumbersEasy(int rangeBegin, int rangeEnd, int count)
{
  // 指定された範囲の整数で埋めたリストを用意する
  List<int> work
    = Enumerable.Range(rangeBegin, rangeEnd - rangeBegin + 1).ToList();

  // workからランダムに取り出して、順に返していく（count回繰り返す）
  var rnd = new Random();
  for (int i = 0; i < count; i++)
  {
    // workからランダムに1つ選んで値を取り出す
    int pos = rnd.Next(0, work.Count);
    int value = work[pos];
    work.RemoveAt(pos); // 取り出した値はリストから取り去る

    // 取り出した値を順に返す
    yield return value;
  }
}

Iterator Function GetUniqRandomNumbersEasy(rangeBegin As Integer, _
                    rangeEnd As Integer, count As Integer) As IEnumerable(Of Integer)
  ' 指定された範囲の整数で埋めたリストを用意する
  Dim work As List(Of Integer) _
    = Enumerable.Range(rangeBegin, rangeEnd - rangeBegin + 1).ToList()

  ' workからランダムに取り出して、順に返していく（count回繰り返す）
  Dim rnd = New Random()
  For i As Integer = 0 To count - 1
    ' workからランダムに1つ選んで値を取り出す
    Dim pos As Integer = rnd.Next(0, work.Count)
    Dim value As Integer = work(pos)
    work.RemoveAt(pos) ' 取り出した値はリストから取り去る

    ' 取り出した値を順に返す
    Yield value
  Next
End Function

分かりやすいロジックで重複しない乱数を生成するメソッド（上：C#、下：VB）
このVisual Basicのコードは、Visual Studio 2012から利用できるようになった反復子を使っている。

　上のメソッドをコンソールアプリから呼び出す例を示す（次のコード）。ダステンフェルドのアルゴリズムに掲載したコードと重複する部分は省略している。

WriteLine("1〜10の整数から3個");
WriteNumbers(GetUniqRandomNumbersEasy(1, 10, 3));
// 出力例： 8, 9, 7

WriteLine("-5〜5の整数から11個");
WriteNumbers(GetUniqRandomNumbersEasy(-5, 5, 11));
// 出力例： 2, 4, 1, -1, -4, 0, 5, -3, 3, -5, -2

WriteLine("1〜52の整数から10個");
WriteNumbers(GetUniqRandomNumbersEasy(1, 52, 10));
// 出力例： 38, 43, 40, 28, 10, 29, 48, 21, 52, 13

WriteLine("1〜10の整数から3個")
WriteNumbers(GetUniqRandomNumbersEasy(1, 10, 3))
' 出力例： 8, 9, 7

WriteLine("-5〜5の整数から11個")
WriteNumbers(GetUniqRandomNumbersEasy(-5, 5, 11))
' 出力例： 2, 4, 1, -1, -4, 0, 5, -3, 3, -5, -2

WriteLine("1〜52の整数から10個")
WriteNumbers(GetUniqRandomNumbersEasy(1, 52, 10))
' 出力例： 38, 43, 40, 28, 10, 29, 48, 21, 52, 13

分かりやすいロジックを呼び出すコンソールアプリの例（上：C#、下：VB）
ダステンフェルドのアルゴリズムとは結果が異なる。ダステンフェルドでは未使用の整数の位置が入れ替わっていくのに対して、このロジックでは未使用の整数の前後関係は変わらないという違いによるものだ（最初の1個だけはどちらのロジックでも同じになる）。

　気になるのは処理速度の違いだろう。コレクションから要素を取り去る操作は時間がかかるので、ダステンフェルドのアルゴリズムよりも遅いと予想できる。実際に、次のようなコードをリリースビルドして何回か実行してみてもらいたい。十倍以上の速度差があるのだが、10万個を取得しても大して待たされないはずだ。数千個のオーダーまでであれば、どちらのロジックを使っても実用上の差は出ないだろう。

WriteLine("10万個の整数から10万個");

var stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
var results1 = GetUniqRandomNumbers(1, 100000, 100000).ToList();
stopwatch.Stop();
WriteLine($"GetUniqRandomNumbersで{results1.Count/10000}万個: {stopwatch.ElapsedMilliseconds}mSec");

GC.Collect();

stopwatch.Restart();
var results2 = GetUniqRandomNumbersEasy(1, 100000, 100000).ToList();
stopwatch.Stop();
WriteLine($"GetUniqRandomNumbersEasyで{results2.Count / 10000}万個: {stopwatch.ElapsedMilliseconds}mSec");

WriteLine("10万個の整数から10万個")

Dim stopwatch = New System.Diagnostics.Stopwatch()
stopwatch.Start()
Dim results1 = GetUniqRandomNumbers(1, 100000, 100000).ToList()
stopwatch.Stop()
WriteLine($"GetUniqRandomNumbersで{results1.Count / 10000}万個: {stopwatch.ElapsedMilliseconds}mSec")

GC.Collect()

stopwatch.Restart()
Dim results2 = GetUniqRandomNumbersEasy(1, 100000, 100000).ToList()
stopwatch.Stop()
WriteLine($"GetUniqRandomNumbersEasyで{results2.Count / 10000}万個: {stopwatch.ElapsedMilliseconds}mSec")

2つのロジックの処理速度を計測するコード例（上：C#、下：VB）
生成された乱数列をローカル変数results1／results2に格納してWriteLineメソッドの中で使うようにしている。そうしておかないと、リリースビルドの最適化によって乱数を生成するメソッドの呼び出しそのものが削除されてしまう可能性があるからだ。
ちなみに筆者の環境では、GetUniqRandomNumbersEasyメソッドの方で250〜280ミリ秒という結果になった。これは10万個を生成させた結果であるから、それよりも2桁少ない数千個のオーダー程度までであれば実用上の違いは分からないだろう。

まとめ

　指定した範囲の整数から重複しない乱数を生成するロジックを2つ紹介した。ダステンフェルドのアルゴリズムは高速だがちょっと難解だ。本稿の後半で示したように、まず分かりやすいロジックで実装し、実際の処理時間を計測し、その処理速度では問題だと判明してから高速化に取り組もう。

利用可能バージョン：.NET Framework 3.5以降
カテゴリ：クラスライブラリ　処理対象：乱数
使用ライブラリ：Randomクラス（System名前空間）
関連TIPS：乱数を生成するには？
関連TIPS：Listに要素を追加／挿入するには？［C#／VB］
関連TIPS：一時ファイル用のランダムなファイル名を生成するには？［2.0のみ、C#、VB
関連TIPS：処理時間を正確に計測するには？［2.0のみ、C#、VB］
関連TIPS：Stopwatchクラスで時間計測をリセットして再開するには？［4以降、C#、VB］
関連TIPS：構文：クラス名を書かずに静的メソッドを呼び出すには？［C# 6.0］
関連TIPS：VB.NETでクラス名を省略してメソッドや定数を利用するには？
関連TIPS：数値を右詰めや0埋めで文字列化するには？［C#、VB］
関連TIPS：構文：メソッドやプロパティをラムダ式で簡潔に実装するには？［C# 6.0／7.0］
関連TIPS：Visual Studioでコンソール・アプリケーションのデバッグ実行時にコマンド・プロンプトを閉じないようにするには？

■この記事と関連性の高い別の.NET TIPS

• 乱数を生成するには？

「.NET TIPS」