パーフェクトシャッフル

パーフェクトシャッフルとは、トランプカードのシャッフルの方法の一つ。カードを完全に二等分して両手に持ち、完全に一枚ずつ左右のカードを重ねるシャッフル方法のこと。

上記の通りであるので、どのように混ざるかは完全に計算できる。面白いことに52枚のカードを8回パーフェクトシャッフルする事で、完全にシャッフル前の状態に戻ることが知られている。

本稿ではそれをJavaScriptで計算してみよう

定式化・アルゴリズム

カードの枚数を 2N 枚とする。一番上を 0番目のカード、その下を 1番目のカードと呼ぼう。右手に 0番目〜 N-1番目のカードを持ち、左手に N番目〜2N -1番目のカードを持つ。シャッフルは、左手のカードから行い、右手のカードの一番上がシャッフル後の 0番目になるようにシャッフルするとしよう。

この時、シャッフル前の x番目が シャッフル後の y番目にくるとして、 y = f(x) なる関数 f を定式化しよう。

簡単な問題だが、少し詳しく見て行こう。シャッフル後の0番目がもともとの何番目か？を考慮すると、f(0)=0 となる。同様に f(N)=1, f(1)=2, f(N+1)=3 ...となる。規則性が見えてきた。

ようは x の値が小さいうち（右手の場合）は f(x) = 2x として良さそうだ。x の値が大きい時（左手の場合）は f(x) = 2x - 2N + 1とすれば良い。つまり、以下のように実装できる。関数ps はシャッフルするオブジェクトの配列を入力に取り、シャッフル後のオブジェクトの配列を返す。オブジェクトはコピーしない、つまり、シャローコピーである点に注意。

function ps(arr) {
  const N = arr.length / 2;
  const ret = new Array(arr.length);
  for (let i = 0; i < N; i++) {
    ret[2 * i] = arr[i];
  }
  for (let i = N; i < 2 * N; i++) {
    ret[ 2 * i - 2 * N + 1] = arr[i];
  }
  return ret
}

こんな感じで使う＆動作確認。

const a = Array(10).fill(0).map(() => Object());
const b = ps(a);
console.log(a[0] !== a[1]); // true
console.log(a[0] === b[0]); // true 0 -> 0
console.log(a[1] === b[2]); // true 1 -> 2
console.log(a[5] === b[1]); // true N ->  1
console.log(a[9] === b[9]); // true 2N-1 ->  2N - 1

何回のシャッフルで戻るか？

以下のように equals 関数を定義することで、元に戻ったかを確認できる。

function equals(arr1, arr2) {
  return arr1.every((val, i) => val === arr2[i]);
}

52枚のカードでパーフェクトシャッフルをして8回目に戻ることを確認しよう

const arr = Array(52).fill(0).map(()=>Object());
let shuffled = arr;
for (let i = 0; i < 16; i++) {
  shuffled = ps(shuffled);
  console.log(`${i + 1}th: ${equals(arr, shuffled)}`);
}

出力はこんな感じ。予想通り。

1th: false
2th: false
3th: false
4th: false
5th: false
6th: false
7th: false
8th: true
9th: false
10th: false
11th: false
12th: false
13th: false
14th: false
15th: false
16th: true

数学的な考察

フェルマーは、2N-1 が素数なら、2N-2 回のパーフェクトシャッフルが必要であることを示した。2N-1 が合成数 p * q の場合（例:トランプの場合)はもっと少なくて、最大でも (p -1) * (q -1)回で済む。52枚のカードの場合は、最大で32回あればよいのだが、前述のとおり、8回ですんだ。

参考文献: 数学の国のミステリー ISBN978-4-10-50631-9