>ところで、このアルゴリズムではコピー元が一意に決定されている(0〜(size-1) まで)。ここもランダムに決定し、この交換を size 回繰り返すような場合、つまり、
>
>void shuffle(int music[], int size)
{
int i;
for (i = 0; i < size; i++) {
int r1 = random(0, size);
int r2 = random(0, size);
int m = music[r1];
music[r1] = music[r2];
music[r2] = m;
}
}
>
>という場合は正しいシャッフルになるのだろうか？ または、これを size 回ではなく、ある他の回数だけ繰り返した場合に正しいシャッフルになるケースはあるのだろうか？
>
>えーと、あんましちゃんと考えてないのだけど、上と同じ論法で無理っぽい気がする。配列をシャッフルするときにはこういうアルゴリズムにすると良いのでは、という話はよく聞く気がするのだけど……。
>
>ところで、少し前に ruby-list でそういう話題があったなあと思って見てみて発見したのが
>ruby-list:40892
>。 C で書きなおすと、
>
>void shuffle(int music[], int size)
{
int i;
for (i = 0; i < size; i++) {
int r = random(0, i+1);
int m = music[i];
music[i] = music[r];
music[r] = m;
}
}
>
>というわけでもとの問題に非常によく似ているが、これは実際に正しいシャッフルであることが
>ruby-list:40896
> で証明されている。上の論法でいっても、この場合はバリエーションがsizeの階乗なので問題がない(かもしれないだけで実際には重複がないか調べないといけない)という次第だ。
>
