乱順再生によってデ-配列の乱すアルゴリズムFisher-Yates Shuffleを開きました

以前はHTML 5のAudio APIで音楽スペクトル効果を書いていましたが、その後にプレイリストを追加すると簡単なプレーヤーになりました.その中で「Shuffle」、つまり一般的なプレーヤーにあるリストの乱れ機能、あるいはランダム再生と理解されました.
しかし、ランダム再生は絶対に実現したほうがいいと思います.Mathを使います.random()は1から曲の数の間の乱数を生成すればよい、そしてplayer.Play(乱数).
リストの乱れは、1つはインタフェースに表示され、曲の順序がランダムに並べられ、2つは再生順序が変わらず、どこがどこなのか、ただその位置の曲が他の曲になっている可能性があります.抽象的には配列要素の再配置であり,具体的なアルゴリズムは探究に値する.
新しい問題に直面したとき、私はまず前の人が問題の答えを出したかどうかを考えました.予想通り、この成熟したFisher-Yates乱序アルゴリズムが発見された.これは古典的なトランプアルゴリズムとして公認されている.しかし、事はここまで終わっていない.
原文は3つの順序が漸近する例を示しており、以下では見る.
一般化方法
原文が導入した現実的な状況はこのようにして、もしあなたがトランプを洗うならば、最もランダムな方法は間違いなくトランプの山の中から勝手に1枚引き出して、それから片側に置いて、それから残りのトランプの中から前の操作を繰り返して、すべてのトランプが別の山の中に引き出されるまで.コード世界に抽象化するには、同じ方法で、配列から1つの要素をランダムに取り出し、別の配列に保存し、元の配列のすべての要素が処理されるまで繰り返します.
原文のプレゼンテーションは直感的ではないと思います.下には自分で書いたアニメーションがあります.このアルゴリズムの手順を説明します(ここで確認することもできます.http://sandbox.runjs.cn/show/1hylhpck ):
次はこの考え方の実現です.

function shuffle(array) {
    var copy = [],
        n = array.length,
        i;
    //           。。。
    while (n) {
        //         
        i = Math.floor(Math.random() * array.length);
        //               。。
        if (i in array) {
            copy.push(array[i]);
            delete array[i];
            n--;
        }
    }
    return copy;
}

copy配列を作成し、ターゲット配列を巡回し、その要素をcopy配列にコピーし、ターゲット配列から削除します.これにより、次回の巡回時にこのシーケンス番号をスキップできます.この実装の問題はここにあり、1つのシーケンス番号の要素が処理されたとしても、ランダム関数によって生成された数がランダムであるため、この処理された要素シーケンス番号はその後のサイクルで絶えず現れる可能性があります.1つは効率の問題であり、もう1つは論理の問題であり、永遠に実行できない可能性があります.
Note:Math.random()が[0,1]を生成する小数delete操作は配列要素の値のみを削除するが配列長には影響せず、削除後元の位置の値がundefinedになる
改善されたアプローチ
上記の解析では問題点が明らかになったので,改善された方法は1つの要素を処理した後,Arrayのsplice()法でターゲット配列から除去するとともにターゲット配列の長さも更新することであり,これにより次回の遍歴時には新しい長さから処理を繰り返すことはない.
アニメーションプレゼンテーション(http://sandbox.runjs.cn/show/v6a7gq0f)

function shuffle(array) {
    var copy = [],
        n = array.length,
        i;
    //        。。
    while (n) {
        //         
        i = Math.floor(Math.random() * n--);
        //        
        copy.push(array.splice(i, 1)[0]);
    }
    return copy;
}

再最適化された最終バージョン
上のやり方はもういいですが、上の改善にはまだ向上の余地があります.配列要素を削除するためにspliceを呼び出すと、削除位置後のすべての要素がshift操作で前方に補完され、配列長を小さくする目的を達成します.もちろん、バックグラウンドで自動的に完了しますが、アルゴリズムの複雑さが増すに違いありません.
配列要素を並べ替えるだけで、すでに取り出された要素と残りの要素の和は配列の元の総要素の個数に等しいことに気づきました.したがって、抽出された要素を保存するために新しい配列を作成しないことを考慮することができます.このようにして、ランダムに配列から1つの要素を抽出し、最後の要素と交換することは、このランダムに抽出された要素を配列の一番後ろに置くことに相当し、それはすでにランダムに通過したことを示し、同時に交換された要素が前に走ったことを示します.後続の繰り返し操作でランダムに削除されます.1回の操作の後、次のラウンドでは、残りのn-1要素、すなわち配列の前のn-1要素で、1つ目まで同じ操作を行います.
アニメーションプレゼンテーション(http://sandbox.runjs.cn/show/jabgttzr):

function shuffle(array) {
    var m = array.length,
        t, i;
    //        …
    while (m) {
        //         …
        i = Math.floor(Math.random() * m--);
        //          
        t = array[m];
        array[m] = array[i];
        array[i] = t;
    }
    return array;
}

より簡潔なバージョン
以上,各言語で広く実装されているFisher−Yates乱順アルゴリズムを紹介した.しかし、JavaScriptについては、配列に付属するsort()メソッドと組み合わせて、より簡潔なコードを作成して目的を達成することができます.中間変数や値交換などは省け、バックグラウンド実装では必ず値交換が行われるが、私たちは気にせずsort()に任せて自分で処理させる.しかし、この方法も簡潔であるため、配列要素が多くなるにつれてランダム性が悪くなるため、上記のアルゴリズムに及ばない.

function shuffle(array) {
    return array.sort(function() {
        return Math.random() - 0.5
    });
}

 
REFERENCE

Fisher–Yates Shuffle: http://bost.ocks.org/mike/shuffle/

Why the Fisher-Yates Shuffle is the best algorithm from Quora: http://www.quora.com/Algorithms/Are-there-any-better-shuffling-algorithms-than-Fisher%E2%80%93Yates-shuffle

45 Useful JavaScript Tips, Tricks and Best Practices http://flippinawesome.org/2013/12/23/45-useful-javascript-tips-tricks-and-best-practices/