欧拉计划 发表于 2016-9-15 01:10:18

题目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 发表于 2017-9-21 16:51:14

递归解法，用functools的lru_cache来加速
from functools import lru_cache
@lru_cache(maxsize=None)
def p172(digits_left=18, digit_count=tuple(*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 == 3 : continue # skip used up digits

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

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

    return possible

print(p172())
227485267000992000
页: [1]
查看完整版本: 题目172：考察只有少量重复位的数字