5つの玉を並べて隣り合うものの和が1〜21になる組み合わせを答える問題

fiveballs.py

# coding: utf-8

'''
「さて 、では 、もう一つ問題を出そう 。
五つのビリヤ ードの玉を 、真珠のネックレスのように 、リングにつなげてみるとしよう 。
玉には 、それぞれナンバが書かれている 。
さて 、この五つの玉のうち 、幾つ取っても良いが 、隣どうし連続したものしか取れないとしよう 。
一つでも 、二つでも 、五つ全部でも良い 。しかし 、離れているものは取れない 。
この条件で取った玉のナンバを足し合わせて 、 １から 2 1までのすべての数ができるようにしたい 。
さあ 、どのナンバの玉を 、どのように並べて 、ネックレスを作れば良いかな ？」

森 博嗣（1996）『笑わない数学者  MATHEMATICAL GOODBYE』講談社.
'''

import itertools

def isMatch(pattern, num, n):
    tempPattern = pattern + pattern
    for i in range(n):
        add = 0
        for j in range(n):
            add += tempPattern[i+j]
            if add == num:
                return True

def isAllMatch(pattern, match, n):
    if(sum(pattern) >= max(match)):
        cnt = 0
        for i in match:
            if isMatch(pattern, i, n):
                cnt += 1
        if cnt == len(match):
            return True


if __name__ == '__main__':

    n = 5
    balls = range(1, 15+1)
    match = range(1, 21+1)

    c = list(itertools.combinations(balls, n))
    patterns = reduce(lambda a,b: a+b, [list(itertools.permutations(x)) for x in c])

    for pattern in patterns:
        if(isAllMatch(pattern, match, n)):
            print(pattern)


'''
結果
(1, 3, 10, 2, 5)
(1, 5, 2, 10, 3)
(2, 5, 1, 3, 10)
(2, 10, 3, 1, 5)
(3, 1, 5, 2, 10)
(3, 10, 2, 5, 1)
(5, 1, 3, 10, 2)
(5, 2, 10, 3, 1)
(10, 2, 5, 1, 3)
(10, 3, 1, 5, 2)
'''

総当りで条件に合うものを列挙したものの、
ちゃんと解き方考えればもっと計算量少なく出来たのかなと

作中の言葉を借りるとエレガントでは無いな