Pythonで場合の数 itertools - みーのぺーじ

Pythonのitertoolsというモジュールを見つけたのですが，これが非常に便利なのでメモしておきます．

例えば以下の問題を解くPythonスクリプトを書いてみます．

身長がみな異なる6人の子供がいます．この6人の子供が次の条件で一列に並びます．
条件1:一番身長の高い子供は端には並ばない．
条件2:一番身長の高い子供から左へ順に身長が低くなるように並ぶ．
条件3:一番身長の高い子供から右へ順に身長が低くなるように並ぶ．
さて，以上のすべての条件に合う並び方は全部で何通りありますか？

算数としては簡単ですね．みーは以下の様に解きました．

背の高い順番に数字で子供を表記するとして，以下の2つの場合を考えます．
1) X1XXXX
2) XX1XXX

1)の場合は，1の右側のXを2から6のうち１つ選べば残りは自動で決まりますので，5通り．
2)の場合は，1の右側のXXを2から6のうち２つ選べば残りは自動で決まりますので，5C2 = 10通り．
上記のすべての場合において，左右対称のものが存在するので2倍して，(5+10)*2=30通り，と分かります．

しかし，子供の数がn人と一般化されると大変です．n人の場合を求めるPythonスクリプトをitertoolsモジュールを使って作ってみました．

import itertools
answer = 0
child_number = 6
def check(i):
    if i[0]==1 or i[child_number-1]==1: # 条件1
        return False
    j = i.index(1) # 最も背の高い子の位置を取得
    # 条件2
    for a in range(0,j-1):
        if i[a]<i[a+1]:
            return False
    # 条件3
    for a in range(j, child_number-1):
        if i[a]>i[a+1]:
            return False
    return True

for i in itertools.permutations(range(1, child_number+1)):
    if check(i):
        print(i)
        answer+=1
print("answer: {0}".format(answer))

child_numberは子供の数で，itertools.permutations()を使って指定したリストのパーミュテーション(順列)を返してくれます．

これをPython3.3で実行すると，以下のようになりました．

(2, 1, 3, 4, 5, 6)
(3, 1, 2, 4, 5, 6)
(3, 2, 1, 4, 5, 6)
(4, 1, 2, 3, 5, 6)
(4, 2, 1, 3, 5, 6)
(4, 3, 1, 2, 5, 6)
(4, 3, 2, 1, 5, 6)
(5, 1, 2, 3, 4, 6)
(5, 2, 1, 3, 4, 6)
(5, 3, 1, 2, 4, 6)
(5, 3, 2, 1, 4, 6)
(5, 4, 1, 2, 3, 6)
(5, 4, 2, 1, 3, 6)
(5, 4, 3, 1, 2, 6)
(5, 4, 3, 2, 1, 6)
(6, 1, 2, 3, 4, 5)
(6, 2, 1, 3, 4, 5)
(6, 3, 1, 2, 4, 5)
(6, 3, 2, 1, 4, 5)
(6, 4, 1, 2, 3, 5)
(6, 4, 2, 1, 3, 5)
(6, 4, 3, 1, 2, 5)
(6, 4, 3, 2, 1, 5)
(6, 5, 1, 2, 3, 4)
(6, 5, 2, 1, 3, 4)
(6, 5, 3, 1, 2, 4)
(6, 5, 3, 2, 1, 4)
(6, 5, 4, 1, 2, 3)
(6, 5, 4, 2, 1, 3)
(6, 5, 4, 3, 1, 2)
answer: 30

答えが30と分かりました．ちなみに7人の子供だと62通り，10人の子供だと510通りになります．便利ですね．

ただし，このPythonスクリプトはnが15とかになるととてつもなく時間がかかりますので，より多くの人数の子供を考える場合はもう少し最適化が必要みたいです．

itertoolsにはpermutations()の他に以下のような便利な関数があるようなので，使ってみると楽しそうです．

product()p, q, ... [repeat=1]デカルト積、ネストしたforループと等価
permutations()p[, r]長さrのタプル列, 繰り返しを許さない順列
combinations()p, r長さrのタプル列, 繰り返しを許さない組合せ
combinations_with_replacement()

ちなみにこちら[www.python.org]に書かれている各関数と等価なスクリプトが非常に秀逸なので，眺めていると楽しいです．

問題：並び方の場合の数は？（第９回算数オリンピックファイナル問題より）算数オリンピック問題に挑戦！より引用．