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;
    }
}
Index

© 2019-2020 hassakulab.com, built with Gatsby