Fisher-Yatesシャッフル
2020/10/12
アルゴリズム
コレクションをランダムに入れ替える(シャッフル)アルゴリズム。Fisher-Yates。
要素数Nに対してO(N)
乱数列をN-1個利用する
C#による実装のサンプル
using System.Collections.Generic;
using System.Linq;
public static partial class IListExtensions {
/// <summary>
/// Fisher-Yatesシャッフル の実装
/// </summary>
public static IList<T> Shuffle<T>(this IList<T> list, RandomGenerator rgen) {
IList<T> target = list.ToList();
for (int i = target.Count; i > 1; --i) {
int a = i - 1;
int b = rgen.Range(0, i);
T tmp = target[a];
target[a] = target[b];
target[b] = tmp;
}
return target;
}
}