Hilbert Curve Shuffle

カードを正方形のグリッドに並べ、ヒルベルト曲線がたどる順に拾い直すと、1 つの決まったシャッフルが得られます。空間充填曲線が近い場所を近いまま保つ性質が、並びにどう表れるかを見ます。

ヒルベルト曲線

位数 $n$ のヒルベルト曲線は $2^n \times 2^n$ のグリッドの全マスを 1 度ずつ通ります。マス数は

N = 4^n

で、隣り合うステップは必ず上下左右に 1 マスだけ動きます。曲線に沿って近い 2 点はグリッド上でも必ず近く、この「局所性の保存」が空間充填曲線の要です。

位数

ステップ

64 / 64　(x, y) = (7, 0)

グリッドの色は並べたときの位置（左上から右へ、行ごとに虹色）です。曲線が通ったマスだけ濃く表示しています。拾った順に並べ直すと、下の帯になります。

上が並べたときの順、下がヒルベルト曲線で拾い直した順です。色は元の位置を表すので、下の帯の色の乱れ方がそのままシャッフルの強さになります。

シャッフル前

シャッフル後

虹がバラバラにならず、ある程度まとまった色の帯として残るのが特徴です。曲線が局所性を保つため、近い位置のカードは散らばりきりません。

位置 $i$ に来たカードの元の位置を $\pi(i)$ として、移動距離 $|\pi(i) - i|$ を並べたものです。自己相似な階段状の形が現れます。

1 回

回数

同じシャッフルを繰り返すと、必ずいつか元の並びに戻ります。戻るまでの回数は巡回置換の各サイクル長の最小公倍数です。（スライダーは 60 回までです）

位数 n	デッキ枚数	サイクル数	最長サイクル	動かない枚数	元に戻るまで
1	4	2	3	1	3 回
2	16	6	6	3	30 回
3	64	4	43	1	774 回
4	256	8	132	2	9,240 回
5	1024	10	320	2	410,667,840 回

0 回目（並べたまま）から 1 行ずつ、シャッフルを 1 回かけた並びを積み上げたものです。Riffle Shuffle のページと同じ見方で、グラデーションが崩れてまた揃うまでを追えます。

774 回で元の並びに戻ります（最終行が 0 回目と同じ並びです）。