パーフェクトシャッフルを互換の積で表現する方法についての問題
ここでパーフェクトシャッフルとは2n枚のカードの下半分と上半分が「下上下上」の順で交互に重なるようにシャッフルすることをさす。数式で書くなら上半分(0 <= i < n)を (i + 1) * 2 - 1 に、下半分(n <= i < 2n)を (i - n) * 2 に移す置換とする。
この置換は、2枚のカードの交換(互換)の組み合わせで表現できる。
0┬1 1┴0
0┬┬2 1┴│0 2┬│3 3┴┴1
組み合わせ方は何通りもある。
0┬┬ 3 1┴│ 0 2 │┬4 3 ┴│1 4┬ │5 5┴ ┴2 0┬┬ 3 1┴│ 0 2┬┴┬4 3┴┬┴1 4┬│ 5 5┴┴ 2 0┬┬┬3 1┴││0 2┬│┴4 3┴│┬1 4┬││5 5┴┴┴2
いくつもの組み合わせ方の中で一番美しい組み合わせ方は何か。もちろん「何が美しいか」は定義されていないので自由に定義していい。上の例では「上下対称が前提で、罫線素片(┬とか)の密度が高い方が美しい」という基準で3番目が一番美しいということになっている。
少なくともn=4までは密度100%の図が書けることがわかっている。これが任意のnについて成立するのかどうか、成立しないならもっとよい「美しさ」の定義はあるだろうか、というのが未解決問題。
0┬┬┬4 1┴││0 2┬││5 3│┴│1 4│┬│6 5┴││2 6┬││7 7┴┴┴3
とりあえず対称な密度100%の置換を全部列挙するプログラムを書いてみた。これはn=7。任意のnについてこの置換の組み合わせでパーフェクトシャッフルが作れるかどうか、という問題。nが増えるに従って「対称な密度100%の置換」の個数は指数的に増える(フィボナッチ)ので、パーフェクトシャッフルが作れる可能性が高くなりそうな気がする。
├────────────┤ ├┤├────────┤├┤ ├┤├┤├────┤├┤├┤ ├┤├┤├┤├┤├┤├┤├┤ ├┤├┤├─┤├─┤├┤├┤ ├┤├─┤├──┤├─┤├┤ ├┤├─┤├┤├┤├─┤├┤ ├┤├──┤├┤├──┤├┤ ├┤├───┤├───┤├┤ ├─┤├──────┤├─┤ ├─┤├┤├──┤├┤├─┤ ├─┤├┤├┤├┤├┤├─┤ ├─┤├─┤├┤├─┤├─┤ ├─┤├──┤├──┤├─┤ ├──┤├────┤├──┤ ├──┤├┤├┤├┤├──┤ ├──┤├─┤├─┤├──┤ ├───┤├──┤├───┤ ├───┤├┤├┤├───┤ ├────┤├┤├────┤ ├─────┤├─────┤
0 1 2 3 4 5 ├┤├┤├┤ ├────┤ ├─┤├─┤ 3 0 4 1 5 2 0 1 2 3 4 5 6 7 ├┤├──┤├┤ ├──┤├──┤ ├──────┤ 4 0 5 1 6 2 7 3
ここまでは僕が人力で解いた。次が人力ではちょっと難しくてプログラムで解く方を選んだn = 5のケース
0 1 2 3 4 5 6 7 8 9 ├─┤├┤├┤├─┤ ├───┤├───┤ ├─┤├──┤├─┤ ├┤├────┤├┤ ├──┤├┤├──┤ 5 0 6 1 7 2 8 3 9 4
ふむふむ。確かにこれであっている。コンピュータ様は賢い。n=6もすぐにでる。
0 1 2 3 4 5 6 7 8 91011 ├┤├─┤├┤├─┤├┤ ├─┤├─┤├─┤├─┤ ├──┤├┤├┤├──┤ ├┤├┤├──┤├┤├┤ ├┤├──────┤├┤ 6 0 7 1 8 2 9 310 411 5
n=7も1.5分くらいかかったけど結果は出た。
0 1 2 3 4 5 6 7 8 910111213 ├┤├┤├┤├┤├┤├┤├┤ ├─┤├┤├──┤├┤├─┤ ├─────┤├─────┤ ├┤├┤├┤├┤├┤├┤├┤ ├┤├────────┤├┤ 7 0 8 1 9 210 311 412 513 6
nが増えるに従って木の分岐の数が指数的に増えるわけだから大変だ。n=8はこの方針では計算できなさそうだ。いま、ゴールへの距離は単調非増加という条件で探索をしているけど、これを単調減少に強めるとn=8では答えが見つからない。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |--| |--| |-----| |--| |-----| |--| |--| |-----| |--| |--------------| |--| |-----| |--| |--| |--| |--------| |--| |--| |--| |--| |--------------------------------| |--| |--------------------| |--------------------| 8 0 9 1 10 2 11 3 12 4 13 5 14 6 15 7
チューニングしたら30秒でn = 8が終わるようになった。ちなみにn = 7が90秒から3秒に縮んだけど、それでn = 8が30秒なわけなので、n = 9はまあ大変そうだ。
