题目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来加速

1. from functools import lru_cache
   
2. @lru_cache(maxsize=None)
   
3. def p172(digits_left=18, digit_count=tuple([0]*10)):
   
4. 
   
5.     # end case, no more digits left
   
6.     if digits_left == 0: return 1
   
7. 
   
8.     possible = 0
   
9. 
   
10.     # try ALL THE DIGITS!
    
11.     # start with min 1 at first digit to prevent leading zeros
    
12.     for n in range(1 if digits_left==18 else 0, 10):
    
13. 
    
14.         if digit_count[n] == 3 : continue # skip used up digits
    
15. 
    
16.         # make modifiable copy (list) and mark digit as used +1
    
17.         tmp = list(digit_count)
    
18.         tmp[n] += 1
    
19. 
    
20.         possible += p172(digits_left-1, tuple(tmp))
    
21. 
    
22.     return possible
    
23. 
    
24. print(p172())

复制代码

227485267000992000
[Finished in 7.9s]