Project Euler 172

プロジェクトオイラー
http://projecteuler.net/index.php

Q172.
頭が0でない18桁の数で、同じ数字を3つより多く使っていないものの個数。

まず、18を3以下の数に分割する。それぞれの分割について対応する数を数える。例えば8を[3, 2, 2, 1]と分割すると、12341231という数がそれに対応する。この分割をそれぞれの数の個数にまとめると、1が1個、2が2個、3が1個だから、[0, 1, 2, 1]。まず、1がどの数字に対応するかが₁₀C₁通り、どこに配置するかが₈C₁通り、2がどの数字に対応するかが₉C₂通り、どこに配置するかが₇C₂₅C₂通り、3がどの数字に対応するかが₇C₁通り、どこに配置するかが₃C₃通りとなる。
しかし、これでは最初の0を排除できない。0が頭で3つ以内使われている個数を削除する。

def gen_div(n, m, l):

    if l == 1:

        if n <= m:

            yield [ n ]

    elif n <= m * l:

        for k in range(1, min(n, m) + 1):

            if k == n:

                yield [ n ]

            else:

                for a in gen_div(n - k, k, l - 1):

                    yield [ k ] + a
def combination(n, m):

    c = 1

    for k in range(1, m + 1):

        c *= (n - k + 1)

        c /= k

    return c
# [ 3, 2, 2, 1 ] -> [ 0, 1, 2, 1 ]

def convert(a):

    b = [ 0 ] * (M + 1)

    for e in a:

        b[e] += 1

    return b
def count(a, n = 10):

    m = sum(a)

    p = 1

    b = convert(a)

    for i in range(1, M + 1):

        p *= combination(n, b[i])

        for k in range(b[i]):

            p *= combination(m, i)

            m -= i

        n -= b[i]

    

    return p
def f(n):

    s = sum(map(count, gen_div(n, M, 9)))

    for a in gen_div(n, M, 9):

        tuples = set()

        for i in range(len(a)):

            tuples.add(tuple(a[:i] + a[i+1:]))

        for t in tuples:

            n0 = sum(a) - sum(t)

            s -= count(t, 9) * combination(sum(a) - 1, n0 - 1)

    return s
N = 6

M = 3

print f(N)