トランプを半分に分け正確にシャッフルする作業を８回繰り返すと順番が元に戻る

今週のトリビアの泉は野球放送延長のため後半が録れてなかったのですがｗ、ruby-list のシャッフルに関するスレをつらつらとながめていて、そういえばそんなのが先週あったなと。

| cards |

cards := 1 to: 13 * 4.

8 timesRepeat: [

   | firstHalf latterHalf shuffled |

   firstHalf := cards first: cards size // 2.
   latterHalf := cards last: cards size // 2.

   shuffled := OrderedCollection new.
   firstHalf with: latterHalf do: [: aa : bb | shuffled add: aa; add: bb].

   cards := shuffled].

^ cards asArray isSorted

=> true

コレクションが an ArrayedCollection でないと isSorted を受けてくれないので、さいごに asArray しないといけないのがちょっとアレですが(^_^;)。

シャッフルする作業は関数（ブロック）にしてもいいかも…と。

| cards doShuffle |

cards := 1 to: 13 * 4.

doShuffle := [: collection |
   | firstHalf latterHalf shuffled |
   firstHalf := collection first: collection size // 2.
   latterHalf := collection last: collection size // 2.
   shuffled := OrderedCollection new.
   firstHalf with: latterHalf do: [: aa : bb | shuffled add: aa; add: bb].
   shuffled].

8 timesRepeat: [cards := doShuffle value: cards].

^ cards asArray isSorted

こっちのほうが、“８回繰り返し”の雰囲気が掴みやすいですね。

では１３枚ではないときはどうなのか、そのとき元に戻るには何回必要なのかもついでに。

World findATranscript: nil.

(1 to: 15) do: [: nn |

   | cards doShuffle count |

   cards := 1 to: nn * 4.

   doShuffle := [: collection |
      | firstHalf latterHalf shuffled |
      firstHalf := collection first: collection size // 2.
      latterHalf := collection last: collection size // 2.
      shuffled := OrderedCollection new.
      firstHalf with: latterHalf do: [: aa : bb | shuffled add: aa; add: bb].
      shuffled].

   count := 1.
   [(cards := doShuffle value: cards) asArray isSorted] whileFalse: [count := count + 1].

   Transcript cr; show: (nn -> count) printString]

トランスクリプト（Smalltalk システムの標準出力もどき）への出力はこんなかんじ。

 1 ->  2
 2 ->  3
 3 -> 10
 4 ->  4
 5 -> 18
 6 -> 11
 7 -> 18
 8 ->  5
 9 -> 12
10 -> 12
11 -> 14
12 -> 23
13 ->  8
14 -> 20
15 -> 58

なるほど、１３枚４組（５２枚）のときの８回は、その前後の枚数のときにくらべて極端に少ないのですね。マジシャンに常識として活用されるのも分からなくもありません。