大量のデータを、でたらめに並べ替える方法

質問

1000個程度のデータがあり、それを“でたらめ”な順番に並べ替えたいのです。
データは配列DataListに準備済みとなっています。
Math.random()を使えばよいのは分かるのですが、どうすれば効率よくでたらめに並べ替えられるのかが分かりません。
何か良い方法がありましたら、ご教授ください。

回答No.3

leaz024 · ベストアンサー

そんなに難しく考える必要はないと思います。
単純選択ソートアルゴリズムの選択部分をランダムピックアップにすれば、データ数Ｎに対し最大Ｎ－１回の交換でシャッフルできます。
JavaScriptだとこんな感じ。

function Shuffle(card) {
　　for (var i = card.length-1; i > 0; i--) {
　　　　var r = Math.floor(Math.random() * (i+1));
　　　　if (r != i) {
　　　　　　var tmp = card[i];
　　　　　　card[i] = card[r];
　　　　　　card[r] = tmp;
　　　　}
　　}
}

お礼

回答ありがとうございます。
ソートのアルゴリズムを応用するとは考えも付きませんでした！簡単なテストソースで確認したところ、完璧にランダムになりました。ループ数もＮ－１回ということで、今回はこの方法でいこうと思います。
サンプルまで提示していただき、本当にありがとうございました。（#1の補足でゲームを作っている、と書きましたが、カードゲームではなかったりして＾＾；）
他にも回答が付くかもしれないので、締め切りは後日行わせていただきます。

回答No.6

sawayakana_yoru

あ、Nの回数が・・ってランダムにするデータの数のことです。どうでもいいですが、勘違いされるといけないので。。失礼しました

お礼

度々の回答ありがとうございます。２件頂きましたので、まとめてこちらにお礼させていただきます。

> 多分短期ランダムでとる実際の違いでしょう、

ちょっと意味が分からなかったのですが、結局のところ「ループ数 * 乱数発生数 == データ数」という式（No.4より）は「乱数発生総数 == データ数」であり、この回数で乱数に均一性を求める（全データを１回ずつ選ぶ）ことは不可能なので、交換漏れが出るのは仕方がないと思いました。

> Nの回数（→ランダムにするデータの数）が無限大に増えて試行されると通用しそうですと思いましたが、だけど、ランダム周期も考慮せないかんのかな。

これは「乱数発生総数を増やせば通用しそうだ」ということかと解釈している（誤解してたらすみません）のですが、No.4のお礼に書きました通り、ループ数をＮ（＝交換回数）に変えても平均して交換漏れが生じるため、確実にＮ－１回で完了するNo.3さんが提示されたアルゴリズムの方が優れているのではないか、との結論に達したわけです。
※Shuffle()のみを交換し、5000回ずつ試行した結果です。

今回はこのような考察の機会に恵まれ、本当に幸運でした。
どうもありがとうございました。

回答No.5

sawayakana_yoru

多分短期ランダムでとる実際の違いでしょう、
Nの回数が無限大に増えて試行されると通用しそうですと思いましたが、だけど、ランダム周期も考慮せないかんのかな。もっとも問題なのがそんなにこだわるアルゴリズムでもない。。

いま、No3さんお回答をじっくりみてみました。ちょっと考えすぎてたみたいです。やっぱりスマートで最高です。ありがとうございます私もいい機会でした。あ、個人的なことゴメン＾ー＾；

回答No.4

sawayakana_yoru

補足要求がありましたので。回数は1000回のランダムな得る回数でいいかも。２回ランダムにとって、それらを交換するなら500回ループってことで。
1が出るとき1/1000,2が出るとき1/1000,3が出...これらが1000回回るとそれぞれ一回でるー交換される期待になりますから。

お礼

補足にお答えいただきありがとうございます。
No.3さんに倣って以下のような関数を作ってみました。
（sawayakana_yoruさんが仰られたアルゴリズムと違っていたらごめんなさい。）

var N = 1000;
function Shuffle2(list) {
　for (var i = 0; i < N/2; i++) {
　　var r1 = Math.floor(Math.random() * N);
　　var r2 = Math.floor(Math.random() * N);
　　if (r1 != r2) {
　　　var tmp = list[r1];
　　　list[r1] = list[r2];
　　　list[r2] = tmp;
　　}
　}
}

この関数を通したDataListについて、元の配列の並びが３個以上連続して残っている箇所をチェックしてみたところ、平均して３０ヶ所以上もありました。
ループ数をN/2からNに変えても、やはり平均２～３箇所は残っていました。
No.3さんの方法では、N-1回で完全にランダムにできたので、今回はそちらの方法を採ろうと思います。
しかし、色々なアルゴリズムについて検証する機会が得られたのは幸運でした。どうもありがとうございました。

回答No.2

sawayakana_yoru

bool真偽チェックでランダムで入れたのを飛ばす処理ってのが安易に浮かびますがデータ量によりますがこっちのほうが効率がいいかもしれません。

準備済みを利用して、
１０００までのランダムの数を２回得て、配列DataListの要素同士をランダムに交換します。具体的に例えばランダム数を一回目二回目得たのをそれぞれ、k[0],k[1]とおくと、
k = k[0];
k[0] = k[1];
k[1] = k;

この処理をランダム回数繰り返します。もちろん多いほうがいいです。
ここで代入が行われているのは実際オブジェクトだと全体のコピーがされて繰り返す回数が多くなるほどもちろん大きくなりますので、これは準備段階でオブジェクトポインタの利用などするといいでしょうーーーー小さい量場合は気にする必要ありませんー

補足

回答ありがとうございます。
もちろん多い方がいい、とのことですが、交換対象をランダムで選ぶわけですから相当な回数の交換が必要ですよね。適当だと思われる交換回数を算出する式みたいなものはありますでしょうか？
よろしくお願いします。

回答No.1

etosetora

まずデータリストのコピーをつくりdata(0)からdata(999)とする、並べ替え後のデータ用にd(0)からd(999)を作る
ランダマイズで０から９９９の数値を取る　仮にn
data(n)をd(0)にコピーしdata(n)を0クリアする
ランダマイズで次の数値を取る
data(n)が0だったらもう一度ランダマイズから数値をとる
これを繰り返す
d(999)まで済んだら終わり

補足

回答ありがとうございます。
この方法だとd(t)のtが999に近づくにつれ、data(n)が０である確立が高くなりますよね。
できればそういう“損”の少ない、効率の良いアルゴリズムが知りたいのです。
プログラムの勉強のつもりでゲームを作ってみているので、そういう方法がありましたらよろしくお願いします。