Tellur52の日記： 視聴順とsuperpermutationの話。

スラドのタレコミが流されそうだったので。
この話、14話すべて見る順列が14!通りあるのを、
全部の順列を嘗めてみるのに最短何話見ればいいのか、
という不思議なことを考え出すのが奇妙だけど、
どうも、話数の下限として、
W[n]≧n!+(n-1)!+(n-2)!+(n-3) ただしn≧2
を見出したのが新規の話らしい。

ちなみに、nが2～4なら、この下限値ぎりぎりの超順列を簡単に求められる。
2:aba
3:abcabacba
4:abcdabcadbcabdcabacdbacbdacbadcba

4chanの連中はシステマティックに超順列を構成する方法を見出した
ようだが、n≧5では求めた下限の式ギリギリは攻められないような気がする。
傾向として \sum_{k=1}^n k! あたりが下限として適切なようにも見えるがはてさて。

ちなみに、元ネタの部分問題(?)として、
アニメ「涼宮ハルヒの憂鬱」の「エンドレスエイト」の解決しない7話を超順列で見ると
長門の追体験をできるか、
というのがあるが、
W[7]≧5884なので、話中で長門が繰り返した回数(15532回)には及ばない。

n=5のとき

[Tellur52 (36331)]

ちなみに、n=5の場合、
4chanでの下限式の値はW[5]=152であるが、
長さ153の列ならシステマティックに構成できる。

abcdeabcdaebcdabecdabceda
bcadebcadbecadbceadbcaedb
cabdecabdceabdcaebdcabedca
bacdebacdbeacdbaecdbacedb
acbdeacbdaecbdacebdacbeda
cbadecbadcebadcbeadcbaedcba

n=6のとき

[Tellur52 (36331)]

W[6]=867.
システマティックに構成した超順列の長さは873。

abcdefabcdeafbcdeabfcdeabcfdeabcdfea
bcdaefbcdaebfcdaebcfdaebcdfaebcdafeb
cdabefcdabecfdabecdfabecdafbecdabfec
dabcefdabcedfabcedafbcedabfcedabcfeda
bcadefbcadebfcadebcfadebcafdebcadfeb
cadbefcadbecfadbecafdbecadfbecadbfec
adbcefadbceafdbceadfbceadbfceadbcfea
dbcaefdbcaedfbcaedbfcaedbcfaedbcafedb
cabdefcabdecfabdecafbdecabfdecabdfec
abdcefabdceafbdceabfdceabdfceabdcfea
bdcaefbdcaebfdcaebdfcaebdcfaebdcafeb
dcabefdcabedfcabedcfabedcafbedcabfedca
bacdefbacdebfacdebafcdebacfdebacdfeb
acdbefacdbeafcdbeacfdbeacdfbeacdbfea
cdbaefcdbaecfdbaecdfbaecdbfaecdbafec
dbacefdbacedfbacedbfacedbafcedbacfedb
acbdefacbdeafcbdeacfbdeacbfdeacbdfea
cbdaefcbdaecfbdaecbfdaecbdfaecbdafec
bdacefbdacebfdacebdfacebdafcebdacfeb
dacbefdacbedfacbedafcbedacfbedacbfeda
cbadefcbadecfbadecbfadecbafdecbadfec
badcefbadcebfadcebafdcebadfcebadcfeb
adcbefadcbeafdcbeadfcbeadcfbeadcbfea
dcbaefdcbaedfcbaedcfbaedcbfaedcbafedcba