トランプのシャッフル（1）

数学 Perl

名前は知らないが、
トランプの山を半分に分けて、両手に持って、
テーブルにカードを押し付けて親指ではじいて交互に混ぜる方法、
これは、プラスチックのカードだと、テクニックがあって、
正確に1枚ずつ順に混ぜる方法があった。
子供のころよくやってて、
これを何回か間違えずにやると元に戻って、
不思議に思ったものだった。
なぜか分からないが、そのことを久しぶりに思い出した。


例えば、0 1 2 3 4 5のカードがあったなら、
0 3 1 4 2 5とシャッフルする。

52枚のカードをアルファベットの大文字小文字で代用すると、
最初は、



    abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

1回シャッフルすると、



    aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ

繰り返しシャッフルすると、



    anANboBOcpCPdqDQerERfsFSgtGThuHUivIVjwJWkxKXlyLYmzMZ

    aGnTAhNubHoUBiOvcIpVCjPwdJqWDkQxeKrXElRyfLsYFmSzgMtZ

    aqGWnDTkAQhxNeuKbrHXoEUlBRiyOfvLcsIYpFVmCSjzPgwMdtJZ

    aiqyGOWfnvDLTcksAIQYhpxFNVemuCKSbjrzHPXgowEMUdltBJRZ

    aeimquyCGKOSWbfjnrvzDHLPTXcgkoswAEIMQUYdhlptxBFJNRVZ

    acegikmoqsuwyACEGIKMOQSUWYbdfhjlnprtvxzBDFHJLNPRTVXZ

    abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

なんと、8回で元に戻る。



my @a = ('a'..'z', 'A'..'Z');

for(0..8) {

    print join("", @a), "\n";

    @a = operate(@a);

}
sub operate {

    my $max = $#_;

    return map { $_[($_+$max*($_&1))/2] } 0..$max;

}

これは、置換だから、群のことばで言うと、
このシャッフルを生成元とする対称群S52の位数8の部分群が存在するということだろう。
試しに、40枚から60枚で何回で元に戻るか調べてみると、



40 12

42 20

44 14

46 12

48 23

50 21

52 8

54 52

56 20

58 18

60 58

52枚のときだけ8回と小さい。
52枚というのは絶妙な枚数だったのだ。



for my $m(20..30) {

    my $n = $m * 2;

    my @init = 0..$n-1;

    my $counter = 0;

    my @a = @init;

    do {

        @a = operate(@a);

        $counter++;

    } while(join(",", @a) ne join(",", @init));

    printf "%d %d\n", $n, $counter;

}