题目172：考察只有少量重复位的数字

欧拉计划

Investigating numbers with few repeated digits

How many 18-digit numbers n (without leading zeros) are there such that no digit occurs more than three times in n?

题目：

有多少个任何数字都出现不超过三次的 18 位数字？

jerryxjr1220

递归解法，用functools的lru_cache来加速

from functools import lru_cache
@lru_cache(maxsize=None)
def p172(digits_left=18, digit_count=tuple([0]*10)):

    # end case, no more digits left
    if digits_left == 0: return 1

    possible = 0

    # try ALL THE DIGITS!
    # start with min 1 at first digit to prevent leading zeros
    for n in range(1 if digits_left==18 else 0, 10): 

        if digit_count[n] == 3 : continue # skip used up digits

        # make modifiable copy (list) and mark digit as used +1
        tmp = list(digit_count)
        tmp[n] += 1

        possible += p172(digits_left-1, tuple(tmp))

    return possible

print(p172())

227485267000992000
[Finished in 7.9s]