如何优化此功能以返回给定范围内具有唯一数字(即没有重复数字)的整数数量

Question

给定了两个整数的列表(即[1,20]或[10,10000](，我正在尝试创建一个函数，该函数返回范围内的整数数(不包含重复数字的((即8、9、10会计算，但11不计(。当输入列表相对较小时，我在这里编写的代码正常工作，但是当范围很大时效率较小。我该如何提高效率？

good_numbers = 0
current_count = list[0]
while current_count <= list[1]:
    list_of_digits = [int(i) for i in str(current_count)]
    if len(list_of_digits) == len(set(list_of_digits)):
        good_numbers += 1
    current_count += 1
print(good_numbers)

当范围相对较小时，这很好，但是当范围很大时我会收到超时错误。

Answer 1

而无需更改算法，这是一个简单的〜3x速度

In [38]: def a(start, end): 
    ...:     g = 0 
    ...:     for i in range(start, end+1): 
    ...:         s = list(f"{i}") 
    ...:         if len(s) == len(set(s)): 
    ...:             g += 1 
    ...:     return g      
    ...:      

结果：

New 
In [35]: %timeit a(10, 10000)                                                                   
12.1 ms ± 147 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Yours :
In [37]: %timeit b([10, 10000])                                                                 
33.5 ms ± 402 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

编辑：

对于überfaster解决方案，您需要更聪明一点。

例如：基本上，您需要能够在开始和终端之间找到数字的排列。

假设您有NE边界。该操作将简单地计算n位数字，n -1位数，n -2位数字的排列数量的总和...

例如，如果我有3位数字，那么我需要总和为9 (9 * 9( (9 * 9 * 8((尝试使用我或您的代码的边界1，1000 :)

在哪里，

In [80]: %timeit 9 + 9 * 9 + 9 * 9 * 8                                                          
11.2 ns ± 0.13 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

您需要提出算法，例如

In [89]: from functools import reduce
In [90]: def c(start, end): 
    ...:     sl = len(list(f"{start}")) 
    ...:     el = len(list(f"{end}")) 
    ...:     t = 0 
    ...:     for i in range(sl, el): 
    ...:         t += reduce(lambda x, y: x * y, [9 - j for j in range(i - 1)], 9) 
    ...:     return t 
In [91]: %timeit c(10, 10000)                                                                   
7.93 µs ± 46.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

但这缺乏边界值的控件，其中您需要检查可能的值高于开始和低于末端。

您可以看到，最后一个更快的速度是：D，但缺少您需要应用的必要控件

Answer 2

，如果您知道带有n位数字的数量与没有重复的10个元素的置换数量相同，则可以大大加速算法。其中，用n> = 2

乘以9/10(以零开头的删除零件(

例如：
有2位数字 -> 10！/8！* 9/10 = 81
有3位数字 -> 10！/7！* 9/10 = 648
n = 1是一种特殊情况(如果包括零，我们可以用1位数字进行10个可能的数字(

现在，您可以用不重复的数字计算数字的数量，最多只有N数字：
n = 1-> 10
n = 2-> 10 81 = 91
n = 3-> 10 81 739 4536
...

这是一个简单的函数，可以计算它：

from functools import reduce
from operator import mul
@lru_cache(maxsize=32)
def good_numbers(n):
    if n > 10:
        return good_numbers(10)
    if n == 1:
        return 10
    return good_numbers(n - 1) + 9 * reduce(mul, range(10 - n + 1, 10))

print([good_numbers(k) for k in range(1, 5)])

输出是：

[10, 91, 739, 5275]