配列をランダム化する効率的な方法-Shuffleコード

Question

私はインタビューでこの質問をされ、さまざまな解決策を挙げましたが、インタビュアーは確信していませんでした。解決策を見つけたいと思っています。意見を投げてください：

Q：効率的なデータ構造を作成して、iPodにシャッフルを実装します。それはすべての曲を異なるランダムな順序で演奏する必要がありますが、同じ曲を繰り返すべきではありません。 （主にO（n））

解決策の1つは、インタビューの後に考えました。再帰なしでランダム化されたクイックソートを行うことができます。ランダムに、1ピボットO（1）を選択してから、QuickSort O（n）を実行します。今、曲はある程度並べ替えられ、最後まで演奏します。それが終わりに達したら、私は再びランダムなピボットを選択し、このプロセスを何度も繰り返します。

よろしく、セスー

Answer 1

すべての曲を配列に配置します...配列内の各要素について、ランダムな位置に交換します。

Answer 2

あなたは フィッシャー - シャッフル. 。あなたの現在受け入れられている答えが1つのファウルになるので、そのページに記載されている実装エラーに注意してください。

Answer 3

さて、頭に浮かぶ最初の線形時間ソリューション：

すべての曲のリンクされたリストを作成できます。これには、O（n）についてです（挿入が一定の時間操作であることを考えると）。次に、ランダム数を生成し、リストのサイズをモジュロにしてランダムインデックスを取得し、そのインデックスを削除して新しいリストに追加します（どちらも一定の時間操作です）。

各o（n） + aの各o（n） + a 2番目の挿入o（n）の挿入。これは全体的に線形時間解を引き起こします。

編集: ：私は完全にリストの散歩を忘れていました。したがって、代わりに、結果を固定長の配列にすることができます。リンクリストのヘッドをポップし、ランダムインデックスを割り当て、配列を入力します。

Answer 4

ネイト（編集）とブライアンのアルゴリズムはフィッシャーです。 E2％80％93yates_shuffle＃比較_with_other_shuffling_algorithms）。曲のシャッフルを間違えると取るに足らない結果が得られるかもしれませんが、オンラインポーカーゲームのためにシャッフルアルゴリズムを書いている場合は、自分が何をしているのかを確認してください（http://www.cigital.com/news/index.php？ Art＆ArtID = 20）。

Answer 5

私は初心者です。思い浮かぶ解決策を言わせてください。何かが間違っているなら、私に知らせてください。

曲が単独または二重にリンクされたリストに保存されていると仮定しましょう。音楽プレーヤーが開かれるたびに（希望する任意の数）乱れを選択し、リスト内のすべてのkノードを逆転させると、同様に2回または最大3回（希望どおり）を実行します（希望どおり） 2n）またはo（3n）シャッフル時間。最後に、リストの最後のノードへのポインターを持っています。また、曲が聴くたびに（ノードが訪問されます）ノードを削除し、O（1）時間で実行できる最後のノードの横に挿入します。これは、音楽プレーヤーが閉じるまで続きます。

ありがとう、答えの正しさを知りたいと思っています。

Answer 6

あなたが望むのはです フィッシャー - シャッフル. 。 Javaの実装は次のとおりです。

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

それがどのように機能するかは、配列全体を帽子として扱い、ランダムな要素を引っ張り、配列の前面に並べ始めます。その後のすべての要素 i 「バケツに」、前のすべての要素は i シャッフルされています。