From: Shin-ichiro HARA <sinara@...>
Date: 2005-08-10T18:28:51+09:00
Subject: [ruby-list:41017] Re: 配列をシャッフル

原です。

お暑うございます。シャッフルの話の続きでもっと暑くなりま
しょう。:-)

>>原です。

>>  ５２枚のトランプは８回（互い違いの正確な）シャッフルすると
>>  元に戻る

>数学絡みの話題には黙っていられない近岡です。

>例えばトランプが６枚のときは、シャッフルの仕方によって、
>          1 2 3 4 5 6
>       → 1 2 3 と 4 5 6 → 1 4 2 5 3 6
>       → 1 4 2 と 5 3 6 → 1 5 4 3 2 6
>       → 1 5 4 と 3 2 6 → 1 3 5 2 4 6
>       → 1 3 5 と 2 4 6 → 1 2 3 4 5 6
>と４回で元に戻る場合と、
>          1 2 3 4 5 6
>       → 1 2 3 と 4 5 6 → 4 1 5 2 6 3
>       → 4 1 5 と 2 6 3 → 2 4 6 1 3 5
>       → 2 4 6 と 1 3 5 → 1 2 3 4 5 6
>のように３回で元に戻る場合があります。

コンウェイとガイの「数の本」（シュプリンガー・フェアラーク
東京）によると前者をアウト・リッフル、後者をイン・リッフル
と呼ぶらしいですね。Ruby で書くと

  def oriffle(a)
    n = a.size
    [a[0...n/2], a[n/2..-1]].transpose.flatten
  end

  p oriffle([1, 2, 3, 4, 5, 6]) #=> [1, 4, 2, 5, 3, 6]
  
  def iriffle(a)
    n = a.size
    [a[n/2..-1], a[0...n/2]].transpose.flatten
  end
  
  p iriffle([1, 2, 3, 4, 5, 6]) #=> [4, 1, 5, 2, 6, 3]

という感じでしょうか。「52枚のトランプが8回で元に戻る」と
いうのはアウト・リッフルの場合ですね。

  def orbit(a)
    r = []
    begin
      r.push a
      a = yield(a)
    end until a == r[0]
    r
  end
  
  p orbit((1..52).to_a) { |x| oriffle(x) }.size #=> 8


>数学的に面白いと思うは、（シャッフルの仕方によってですが）
>　４枚：４回、１０枚：１０回、１２枚：１２回、１８枚：１８回、…
>と枚数＝回数となる場合があるということです。

この数値はイン・リッフルの場合ですね。「数の本」にはたいした
事は書いてないのですが、これについて詳しく書いてある文書があ
りました。

  http://www005.upp.so-net.ne.jp/mi_kana/story/shuffle.pdf

結論を言うと 2*N 枚のトランプがイン・リッフルで元に戻る回数
が最大(2*N)になるのは

  2*N+1 が素数で (2*N+1) % 8 == 3 か 5

のときみたいですね。

一般のシャッフルfにたいして orbit((1..52).to_a) { |x| f(x) }
のサイズがいくつになるか気になります。52の階乗の約数になるの
は分かるのだけど、それはでかすぎる。これ以上の話はruby-math
ですかね。向こうは（も？）廃れてるし。(^^;


噂によると昔多湖輝の「頭の体操」にこの話が書いてあったそうです。
しかもそこでは「簡単に示す事が出来る」とあったそうなんですが、
「頭の体操」が数論を使うわけないので、簡単にって言う意味は多分
具体的に紙に数字を書いてシャッフルする事だと思います。それが、
今ではコンピュータであっという間に出来てしまうのだから、便利に
なったものですね。