python - 求一个 10 位整数，其中前 n 位数字可以被 1 到 n 整除

Question

寻找一个具有不同数字的 10 位整数，以便前 n 位数字可以从 1 到 n 整除。

一个较小的例子是 123。

1能被1整除
12能被1和2整除
123 能被 1,2 和 3 整除

我写了一些代码来尝试自动执行此操作:

import sympy
import itertools

x = itertools.permutations('1234567890',10)

for s in x:

    string_number = ''.join(s)

    for j in range(1, len(string_number)):

        a = set(range(1,j+1))

        divisors = set( sympy.divisors( int(string_number[:j] ) ) )

        if not (a.issubset(divisors) and a!=divisors):
            break
    print('FOUND IT %s'%string_number)

这似乎行不通，我认为是因为最后一点的逻辑。我如何确保如果一个数字违反条件，我将继续下一个数字，我如何确保如果该数字符合条件，我选择正确的数字进行打印？

Answer 1

无需枚举所有可能的排列，您可以一次创建一个数字，并在该数字到目前为止有效时继续。这是一个基本的深度优先搜索。

您还可以将其作为生成器函数来查找第一个或所有 这样的数字。这是一个相当直接的实现，没有任何优化:

def find_number(stop, number=""):
    if len(number) == stop:
        yield number

    for d in "1234567890":
        if d not in number:
            new_num = number + d
            if int(new_num) % len(new_num) == 0:
                for n in find_number(stop, new_num):
                    yield n

例子:

>>> next(find_number(10))
3816547290
>>> list(find_number(9))
['381654729', '381654720', '783204165', '801654723', '081654327']

---

但是 10! 可能的数字也不是所有那么多，所以如果您可以等待几秒钟，您的详尽方法也应该有效。将其全部放入一个可怕的单行列表理解/生成器表达式中如何？

next(s for s in map(''.join, itertools.permutations('1234567890', 10)) 
     if all(int(s[:i]) % i == 0 for i in range(1, len(s)+1)))

---

如评论中所述，问题似乎出在 break 上，它只是从内部循环中中断，但没有跳过 print 语句。我没有尝试这个，因为我现在没有安装 sympy，但是你应该可以使用 for/else 循环来解决这个问题:

for j in range(1, len(string_number)):
    a = set(range(1,j+1))
    divisors = set( sympy.divisors( int(string_number[:j] ) ) )
    if not (a.issubset(divisors) and a!=divisors):
        break
else:
    print('FOUND IT %s'%string_number)