Fisher-Yates（フィッシャーイェーツ）というアルゴリズムを使って配列やリストを並び替えたいと思います。
アルゴリズムの考え方ですが N 個の要素数があったとして
- 一番最後の要素 (N) をそれ以外の前方の要素とランダムに交換する
- 一番最後から -1個目を前方の要素とランダムに交換する
- -2個目を前方の要素とランダムに交換する
- N-1個目まで繰り返す
と、後ろから前方に範囲を狭めながら要素を好感していき処理が終わると配列の内容が全てシャッフルされるアルゴリズムです。配列に対してこの処理を実行すると内容が不可逆にシャッフルされるのでそれだけ注意しましょう。
処理回数は O(N) だと思うんので計算量はかなり少ないほうだと思います。
実装内容
通常の .NET 向けの処理と Unity 向けの処理を #if で切り替えています。
両環境このままコピペすれば動くはずです。
public static class RandomUtil { // // Unity 向けの実装 // #if UNITY_5_3_OR_NEWER /// <summary> /// Fisher-Yates(フィッシャー・イェーツ) アルゴリズムでコレクションをシャッフルします。 /// </summary> /// <remarks> /// 指定した配列の順序が不可逆に変更されます。 /// </remarks> public static void Shuffle<T>(IList<T> collection) { int n = collection.Count; for (int i = n - 1; i > 0; i--) { int j = UnityEngine.Random.Range(0, i + 1); T tmp = collection[i]; collection[i] = collection[j]; collection[j] = tmp; } } /// <summary> /// Fisher-Yates(フィッシャー・イェーツ) アルゴリズムでコレクションをシャッフルします。 /// </summary> /// <remarks> /// 指定した配列の順序が不可逆に変更されます。 /// </remarks> public static void Shiffle<T>(T[] array) { int n = array.Length; for (int i = n - 1; i > 0; i--) { int j = UnityEngine.Random.Range(0, i + 1); T tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } #else // // .NET 向けの実装 // static readonly Random _rand = new(); /// <summary> /// Fisher-Yates(フィッシャー・イェーツ) アルゴリズムでコレクションをシャッフルします。 /// </summary> /// <remarks> /// 指定した配列の順序が不可逆に変更されます。 /// </remarks> public static void Shiffle<T>(IList<T> collection) { int n = collection.Count; for (int i = n - 1; i > 0; i--) { int j = _rand.Next(0, i + 1); T tmp = collection[i]; collection[i] = collection[j]; collection[j] = tmp; } } /// <summary> /// Fisher-Yates(フィッシャー・イェーツ) アルゴリズムでコレクションをシャッフルします。 /// </summary> /// <remarks> /// 指定した配列の順序が不可逆に変更されます。 /// </remarks> public static void Shiffle<T>(T[] array) { int n = array.Length; for (int i = n - 1; i > 0; i--) { int j = _rand.Next(0, i + 1); T tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } #endif
ちなみに seed 値はできないので再現性は考慮していません。
