找到一个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)