整列してる配列をランダムに並び替える

質問

タイトルのままで
1～Xまで並んでいる配列を、順番をめちゃくちゃにする場合、どのようなアルゴリズムをしようしているのでしょうか？

一応言語の縛りは無しという事で、分かりやすいアルゴリズムがあったらお願いします。

回答No.4

Gotthold · ベストアンサー

（良質な乱数源は既に存在するものとして）
シャッフル手法としてはFisher-Yatesが一番良いです。
アルゴリズムも単純だと思います。

本来シャッフルは線形時間で可能な単純な操作で、
変に工夫してるようなアルゴリズムの方が
大抵おかしな結果（全ての組み合わせが等確率で出現しない）を出します。
（その上遅かったり…。）

例えば、交換する要素の（片方ではなく）両方を乱数で決定して複数回交換する方法は、
まず交換回数を何回にすればよいかが分かりませんし、
実際何回交換しても全組合わせが等確率で出現するようにはならないです。

No.2の回答は惜しい気もしますが、
出現確率が高い組み合わせと低い組み合わせが存在します。
と、これについては前に全く同じ事を言った気がするので探してみたら、
↓の回答で言ってました。

ランダムに複数のリンク、重複なし。[OKWave]
http://okwave.jp/qa4848405.html

回答No.6

Gotthold

> No.5
そのようなシュワルツ変換を利用したシャッフルはそれなり良い結果にはなりますが、
randが同じ値を返すことがあるため
厳密には全ての組み合わせが等確率で出現しません。
また、ソートを行うので計算量も大きいです。

Fisher-Yatesならちゃんと混ざりますし、
計算量も線形オーダーですよ。

回答No.5

notnot

swapするのではなかなかまざりません。

乱数をソートするのでどうでしょうか。
#include <stdio.h>
#include <stdlib.h>
#define X 10

typedef struct { int n; int r; } t;

int cmp(const void *x, const void *y) {
return ((t*)x)->r - ((t*)y)->r;
}

main() {
t a[X];
int i;
srand(time(NULL));
for(i=0; i<X; ++i){
a[i].n = i;
a[i].r = rand();
}
qsort(a, X, sizeof(t), cmp);
for(i=0; i<X; ++i){
printf("%d\n",a[i].n);
}
}

回答No.3

sakusaker7

分かりやすいかどうかは保証できませんが、言語の組み込みやライブラリに
配列のシャッフルがある場合はこれを使っているのが多いと思います。

Fisher–Yates shuffle - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

検索すればいろいろな言語での実装例が見つけられますが、
配列のシャッフル
http://ray.sakura.ne.jp/tips/shaffle.html
ではCによる例があります。

>ちなみに、次のようにしても同様です。STL の random_shaffle と似た感じの方法です。

>for(i = 1; i < N; i++){
> a = rand(i + 1);
> swap(array[i], array[a]);
>}

お礼

いろいろと参考になりそうです。
ありがとうございます。

回答No.2

ssk38

面倒なのでCで書いたけど、こんな感じはどうでしょう。

for (from=0; from < n; from++) {
to = (int)(rand() * n); //0～n-1の整数乱数
swap(from, to, array);
}

これだとデータに対して処理量線形で、
arrayがでかくなってもメモリ使用量はあんまかわらんでできます。

お礼

なるほど。
配列の分だけ処理をするだけですね。
これはこれでさっくりしてていいですね

回答No.1

INTLINSIDE

まず単純に考えるなら。
indexA=random(list.count)
indexB=random(list.count)
swap(list.items[indexA],list.items[indexB])
となるでしょう。
（まあこれだと、配列というかリストですが。
あくまでイメージなので）

で、random関数の中身は、いろいろ考えられると思います。
たくさんあります。
一番簡単なのは、そのまま言語に実装してあるrandom関数を利用することではないでしょうか。

お礼

やはり交換しながらランダムに並び替えていくのが基本的な感じなのでしょうね。
ありがとうございました。