Hatena2009-07-14
code:hatena
<body>
*1247538392*はてなに「iPhoneは携帯じゃない」と言われた件
*1247538890*テスト
iPhoneから送信
*1247545805*パーフェクトシャッフルを互換の積で表現する方法についての問題
ここでパーフェクトシャッフルとは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
||<
<hr>
とりあえず対称な密度100%の置換を全部列挙するプログラムを書いてみた。これはn=7。任意のnについてこの置換の組み合わせでパーフェクトシャッフルが作れるかどうか、という問題。nが増えるに従って「対称な密度100%の置換」の個数は指数的に増える(フィボナッチ)ので、パーフェクトシャッフルが作れる可能性が高くなりそうな気がする。
||
├────────────┤
├┤├────────┤├┤
├┤├┤├────┤├┤├┤
├┤├┤├┤├┤├┤├┤├┤
├┤├┤├─┤├─┤├┤├┤
├┤├─┤├──┤├─┤├┤
├┤├─┤├┤├┤├─┤├┤
├┤├──┤├┤├──┤├┤
├┤├───┤├───┤├┤
├─┤├──────┤├─┤
├─┤├┤├──┤├┤├─┤
├─┤├┤├┤├┤├┤├─┤
├─┤├─┤├┤├─┤├─┤
├─┤├──┤├──┤├─┤
├──┤├────┤├──┤
├──┤├┤├┤├┤├──┤
├──┤├─┤├─┤├──┤
├───┤├──┤├───┤
├───┤├┤├┤├───┤
├────┤├┤├────┤
├─────┤├─────┤
||<
<hr>
||
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はまあ大変そうだ。
*1247576139*日記
ダイソーで100円のサングラスを買ったら眼精疲労のときに照明が眩しくてたまらないのが軽減されてQOLが向上した。
ピーマンは生で食べてもいいということを学習したので今日はピーマン二つとニンジン一本を食べた。野菜充。
*1247579980*LifeGameAction
なかなか面白かった。最初、ジャンプして下に落ちて3回くらい死んだのは秘密。Cで足場を作るのを有効活用しないと行けないね。黄色の雲の上を跳ねながら青の雲と赤の雲の間にグライダーを置いて行く、と。
*1247586103*ファイル添付
メニューが見当たらない。どうやってメールに写真を添付したらいいんだ
iPhoneから送信
発想の転換をして、メールに写真を添付するのではなく、写真をメールで
送信することにした。
iPhoneから送信
追記、iPhoneからメールで写真をフォトライフにアップロードするのはできたが、はてな側の問題で日記に貼り付かなかった。
フォトライフはiPhoneで見ると表示が崩れていて、idのコピーが困難。面倒だなぁー
</body>
![http://gyazo.com/0f2a4974c9fab649c0818e33e732baff.png">](http://gyazo.com/0f2a4974c9fab649c0818e33e732baff.png">){kind=link}
![http://gyazo.com/d9a18e34453e2e75e2f53f5de4dec4e7.png">](http://gyazo.com/d9a18e34453e2e75e2f53f5de4dec4e7.png">){kind=link}