CodeIQ：「超」整理法に従って並べなおして！

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「「超」整理法に従って並べなおして！」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
「超」整理法では「使った順にファイルを並べる」という方法が提唱されています。
例えば、資料を本棚に並べるとき、戻すときは必ず左端に戻す、という方法です。
使っていない資料が自然と右端に押し出されていきます。

このような使い方をしていましたが、ふと最初の順番に戻したくなりました。
最後に使った資料を左端に追加することを繰り返して、元の順番に戻すまでの最短の手順を考えます。

例えば、3冊のファイルで元の配置が左からA, B, Cの順に並んでいれば、
A, B, C　：　0回の移動
A, C, B → (Bを移動) → B, A, C → (Aを移動) → A, B, C　：　2回の移動
B, A, C → (Aを移動) → A, B, C　：　1回の移動
B, C, A → (Aを移動) → A, B, C　：　1回の移動
C, A, B → (Bを移動) → B, C, A → (Aを移動) → A, B, C　：　2回の移動
C, B, A → (Bを移動) → B, C, A → (Aを移動) → A, B, C　：　2回の移動
といった移動で実現できます。

【問題】
標準入力からファイルの冊数が与えられたとき、すべてのパターンを考え、移動回数の合計を標準出力に出力してください。

私のプログラム

Pythonで解答しています。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/local/bin/python3
 
import fileinput
 
'''
    n階乗を求める
'''
def R(n):
    ret = 1
    for i in range (1, n+1):
        ret *= i
    return ret
 
'''
    OEIS A130477を参考(FORMULAの式)
    (ex) n=2(0始まり)の場合、
        T(2,0)  1
        T(2,1)  2
        T(2,2)  3
    となり、問題の0回交換、1回交換、2回交換の回数の組み合わせになる。
'''
def T(n,k):
    if k == 0:
        return 1
    return (n-k+1+0**k)*(R(n+1)//R(n-k+2))
 
'''
    main
'''
if __name__ == "__main__":
    for line in fileinput.input():
        line = line.strip()
        if not line:
            continue
 
    n = int(line)
 
    cnt = 0
    for k in range(n):
        ret = T(n-1,k)
        cnt += ret * k
    print(cnt)

解説

上記のコードは計算だけで効率よく解を求めることができます。
ただし、私はこのコードを最初から考えたわけではありません。実際にはシミュレーションのコードを書き、その結果の数列をOEISで検索して見つけた漸化式をPythonのコードにしたものが上記のプログラムです。
なので、上記のコードの本体であるT()がなぜそうなるのかは分かっておらず、説明できません。

シミュレーション

シミュレーションのコードを示します。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/local/bin/python3
 
import sys
 
Memo = []
All = set()
 
def newArrays(i, n):
    global All
    lsts = Memo[i]
    s = set()
 
    for b in lsts:
        for j in range(1,n):
            h = b[0]
            a = list(b[1:])
            a.insert(j,h)
            a = tuple(a)
            if not a in All:
                All.add(a)
                s.add(tuple(a))
    return s
 
def printMemo():
    for l in Memo:
        print(l)
 
def printMemoCounts():
    for i,l in enumerate(Memo):
        sys.stdout.write(str(i) + ":" + str(len(l)) + " ")
    sys.stdout.write("\n")
 
def solve(n):
    global Memo
    cnt = 0
    for i in range(n-1):
        s = newArrays(i, n)
        cnt += (i+1) * len(s)
        Memo.append(s)
    return cnt
 
if __name__ == "__main__":
    n = int(sys.argv[1])
 
    base = tuple(i for i in range(n))
    All.add(base)
    s = set()
    s.add(base)
    Memo.append(s)
 
    ret = solve(n)
    printMemoCounts()
    print(ret)

このコードはCodeIQの回答コードとは違って入力値を引数にもらうようになっているので注意してください。

これは何をしているのかというと、例えば[A,B,C]という本があった場合、問題の言うところの開始状態の本の並びには次の6とおりがあります。
[A,B,C]、[B,A,C]、[B,C,A]、[A,C,B]、[C,B,A]、[C,A,B]
この並びからルールに従って[A,B,C]に並び直すのも、逆に[A,B,C]の状態から上記の状態を作るのも必要な手順回数は同じです（順番が逆になるだけ）。なので[A,B,C]からできるすべての並び順の組み合わせを「超」整理法の逆の手順で作ることによって回数を求めています。

このプログラムでは最大の入力値（N=15）に近づくと時間切れになりますがその途中のパターン数はわかります。それで、その数列をOEISで検索して調べた漸化式を実装したものが提出したプログラムというわけです。

雑感

実際の所、仕事でプログラムを書く場合、わからないから諦めるというわけには行かないわけで、そのためには調べるという能力はかなり重要です。なので、このように自分で考えてもわからない（性能を満たせない）場合は調べてでもやるというのは結構重要なことだと思います。