パーフェクト・シャッフル#1


リフル・シャッフル(ウォーターフォール・シャッフル などともよばれる)は,カードをシャッフル(混ぜる)方法の1つで,テレビでマジシャンがよくやっている,2つに分けて,カードの端をパラパラと弾いて,交互に噛ませてシャー・・・というやつである.

このシャッフルを完璧に,すなわちキレイに2つに分け,カードを左右1枚のズレもなく噛みあわせてシャッフルすることを,パーフェクト・シャッフルという.今回はよく知られている事実「パーフェクト・シャッフルを繰り返すと初期の配置にもどる」についてのメモを載せる.

なお,本来のパーフェクト・シャッフルはカードの動きこそ同じだが,元となっているシャッフルの方法が異なる(ファロー・シャッフルという).墓穴を掘りそうなのでここではこれ以上言及しないが.

スポンサーリンク

 

本題

さて,パーフェクト・シャッフルは(JOKERを除いた)1組52枚のプレイング・カードに対しては適用できるが,枚数の変動によって細かなエラーが出てきてしまうため,この記事では次のように定義する.

Def 1.1

N (\geqq 2) 枚のカード に対し,パーフェクト・シャッフルを以下の手順で定める.

[1] カードの山を下半分を B, 上半分を T とする.ただし,N が奇数のときは,T の枚数は B の枚数より1枚少ないものとする.

[2] B の一番下のカードの上に T の一番下のカードをおき,その上に B のいま一番下のカード(つまり下から2番目にあったカード)をおいて,\cdots をカードがなくなるまで交互に繰り返す.

具体的な数字の列で動きを確認する.左側を一番下,右側を一番上だとして,N = 10 のとき

    \[ [1,2,3,4,5,6,7,8,9,10] \]

    \[ \Downarrow \]

    \[ B = [1,2,3,4,5] ~,~~~~T = [6,7,8,9,10] \]

    \[ \Downarrow \]

    \[ [1,6,2,7,3,8,4,9,5,10] \]

N = 9 のとき

    \[ [1,2,3,4,5,6,7,8,9] \]

    \[ \Downarrow \]

    \[ B = [1,2,3,4,5]~,~~~~T = [6,7,8,9] \]

    \[ \Downarrow \]

    \[ [1,6,2,7,3,8,4,9,5] \]

のような動きとなる.

Th 1.2
N (\geqq 2) 枚のカードに対するパーフェクト・シャッフルを繰り返すと,いつか必ず初期の配置にもどる.
コメント

 

事実確認

代数学の置換を用いて証明することができるようだが,今回はコンピュータに委託.もちろんこれではすべての自然数で成り立つことは示せないのだが,少なくとも 10000 までの自然数で成り立つことを調べる.まずはパーフェクト・シャッフルの動きを定義.配列をリフル・シャッフルした結果を返す関数を用意する.引数 stack には異なる N 個の連続自然数を要素にもつリストを入れる.

奇数と偶数で場合分けをしている.次に,配列が必ず初期配置にもどると仮定して,もどるまでのシャッフル回数を調べる関数は

としてみた.必要な回数のみを表示するが,2つの#を外すとシャッフルの動きを確認できる.recovery(range(10)) とすると

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 5, 1, 6, 2, 7, 3, 8, 4, 9]
[0, 7, 5, 3, 1, 8, 6, 4, 2, 9]
[0, 8, 7, 6, 5, 4, 3, 2, 1, 9]
[0, 4, 8, 3, 7, 2, 6, 1, 5, 9]
[0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
6 times

を得る.また,recovery(range(52)),recovery(range(54)) の結果はそれぞれ

8 times
52 times

であった.JOKERを除けば8回で,JOKERを2枚入れれば52回で初期配置にもどるようである.2枚の差がかなり顕著に現れた.

Cor 1.3
JOKER を除いた1組52枚のプレイング・カードは,8回のパーフェクト・シャッフルで初期の配置にもどる.

 

カードの枚数を変えて調べてみよう.

とする.m=5 とすると,カードが1枚のときから5枚のときまでの,初期配置にもどるために必要なシャッフルの回数を返す.もっとも,m=1,2 は完全に自明であるが.さて,recovery_test(52) の結果は以下のとおり.

N = 1 : 1 times
N = 2 : 1 times
N = 3 : 2 times
N = 4 : 2 times
N = 5 : 4 times
N = 6 : 4 times
N = 7 : 3 times
N = 8 : 3 times
N = 9 : 6 times
N = 10 : 6 times
N = 11 : 10 times
N = 12 : 10 times
N = 13 : 12 times
N = 14 : 12 times
N = 15 : 4 times
N = 16 : 4 times
N = 17 : 8 times
N = 18 : 8 times
N = 19 : 18 times
N = 20 : 18 times
N = 21 : 6 times
N = 22 : 6 times
N = 23 : 11 times
N = 24 : 11 times
N = 25 : 20 times
N = 26 : 20 times
N = 27 : 18 times
N = 28 : 18 times
N = 29 : 28 times
N = 30 : 28 times
N = 31 : 5 times
N = 32 : 5 times
N = 33 : 10 times
N = 34 : 10 times
N = 35 : 12 times
N = 36 : 12 times
N = 37 : 36 times
N = 38 : 36 times
N = 39 : 12 times
N = 40 : 12 times
N = 41 : 20 times
N = 42 : 20 times
N = 43 : 14 times
N = 44 : 14 times
N = 45 : 12 times
N = 46 : 12 times
N = 47 : 23 times
N = 48 : 23 times
N = 49 : 21 times
N = 50 : 21 times
N = 51 : 8 times
N = 52 : 8 times

単純に枚数が多ければ回数が増えるというわけではなさそうだ.そして今更ながら気が付いたが,奇数→偶数のときには必要回数が等しい.奇数枚のときだけをピックアップし,N = 1 から N = 501 までの結果をグラフにしてみた.


 

値が小さいところについてはなんとも言えないが,値が大きくなる場所については,必要な値がかなり直線的に増加している.

想像以上に面白い実験結果になってしまった.今後続きを書くかもしれないが,今回はここまでにする.

 

結果とは無関係なコメント

某TCG愛好家の人々の間ではリフル・シャッフルが「ショット・ガン・シャッフル」とよばれることもあるようだが,この名称は正式ではない.しかしカードを傷めるのは間違いではないだろう.なお本来「ショット・ガン・シャッフル」というのは次のようなシャッフルを指すと言われている.

カードを上から1枚ずついくつかの山に分けて,最後に重ねるというものである.別名パイル・シャッフル.かなり時間がかかってしまうが,カードを傷めることはそうないだろう.こちらについては,カードの枚数を N 枚とするとき

    \[ N = \ell \times m \]

なる自然数 \ell,m をとると,\ell 個の山に分けてパイル・シャッフルをしたあとに m 個の山に分けてパイル・シャッフルをすれば初期の配置に戻るという性質がある(はず).いずれメモを残すかもしれない.


スポンサーリンク