パスワードを忘れた? アカウント作成
13754429 journal
日記

Tellur52の日記: 視聴順とsuperpermutationの話。 2

日記 by Tellur52

スラドのタレコミが流されそうだったので。
この話、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回)には及ばない。

この議論は、Tellur52 (36331)によって ログインユーザだけとして作成されたが、今となっては 新たにコメントを付けることはできません。
  • by Tellur52 (36331) on 2018年10月27日 9時19分 (#3505382) 日記

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

    abcdeabcdaebcdabecdabceda
    bcadebcadbecadbceadbcaedb
    cabdecabdceabdcaebdcabedca
    bacdebacdbeacdbaecdbacedb
    acbdeacbdaecbdacebdacbeda
    cbadecbadcebadcbeadcbaedcba

    • by Tellur52 (36331) on 2018年10月27日 12時05分 (#3505428) 日記

      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

      親コメント
typodupeerror

目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond

読み込み中...