Fisher–Yates shuffleシャッフルアルゴリズム

1、縁起
[A,B,C,D,E]の2つのB,Eがランダムに配列され、他のデータが元の位置にあるなど、最近の作業で問題が発生しました.
元の配列:[A,B,C,D,E]
ランダム文字:[B,D]
可能な結果:［A,B,C,D,E］,［A,D,C,B,E］
この問題を解決する過程で、解決しなければならない問題の一つは、配列をランダムにソートする方法です.インターネットで調べてみると、これもコンピュータ科学の基礎問題であり、シャッフルアルゴリズム(Shuffle Algorithm)とも呼ばれている.
 
2、問題と解決
2.1、質問
簡単です.配列を指定し、要素をランダムに配置します.例えば、所与の配列arry=>[1,2,3,4,5]である.A 5-5の結果がある5!=120種類の結果
 
2.2、解決
簡単です.白話で言えば:
a、1番目の要素を選択し、n番目の要素のいずれかと交換します(1番目の要素自体を含む).このとき、ソート後の1番目の要素が決定されます.
b,2番目の要素を選択し,n−1番目の要素と任意の交換(2番目の要素自体を含む)を行う.
c、上記の手順を1つの要素が残るまで繰り返します.
 
3.3、コード
そのアルゴリズムを知っていれば、実現は簡単です.

/// <summary>

/// Randomize the list elements using Fisher–Yates shuffle algorithm http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

/// </summary>

/// <typeparam name="T">elements type</typeparam>

/// <param name="list"></param>

public static void Shuffle<T>(this IList<T> list)

{

    Random rng = new Random();

    int n = list.Count;

    while (n > 1)

    {

        n--;

        int k = rng.Next(n + 1);

        T value = list[k];

        list[k] = list[n];

        list[n] = value;

    }

}

 
3.4,その他
このアルゴリズムの複雑さはO(n)であり,偏差はなく,各要素のランダム確率は等しい.確かに良いアルゴリズムです:).
Wikiでは、このアルゴリズムの変種もいくつかありますが、上記のように使いやすく、最初のFisher-Yatesアルゴリズムは使いにくく、複雑度はO(n^2)です.
 
参照先:
http://blog.codingnow.com/2007/09/shuffle.html
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle