Python: 有策略地遍历十位数字 0-9

Question

最近看了一道数学题，启发我写程序。它要求 将数字 0-9 排列一次，以便 xx xxx / xx xxx = 9. 我写了一个 python 程序找到解决方案并在确保数字不同时遇到了一些麻烦。我找到了一种使用嵌套 whiles 和 ifs 的方法，但我对此不太满意。

b,c,x,y,z = 0,0,0,0,0  #I shortened the code from b,c,d,e,v,w,x,y,z
for a in range (10):
    while b < 10:
        if b != a:
            while c < 10:
                if c != b and c != a:
                    while x < 10:
                        if x != c and x != b and x != a:
                            while y < 10:
                                if y != x and y != c and y != b and y != a:
                                    while z < 10:
                                        if z != y and if z != z and y != c and z != b and z != a:
                                            if (a*100 + b*10 + c)/(x*100 + y*10 + z) == 9:
                                                print ()
                                                print (str (a*100 + b*10 + c) + "/" + str (x*100 + y*10 + z)
                                        z += 1
                                    z = 0
                                y += 1
                            y,z = 0,0
                        x += 1
                    x,y,z = 0,0,0
                c += 1
            c,x,y,z = 0,0,0,0
        b += 1
    b,c,x,y,z = 0,0,0,0,0

如您所见，代码非常长且重复，即使是缩短的形式。运行在我的笔记本电脑上 几乎需要一分钟 （我的笔记本电脑是新的）。我已经搜索了答案，但我只找到了生成随机数的方法。我也尝试使用 itertools.permutations，但这只显示排列，而不是创建数字。

生成所有十位数字太长，我想知道是否有更快、更简单的方法，并附有说明，使用python 3..

谢谢

Answer 1

这是使用 itertools 解决此问题的一种方法。

import itertools

def makenum(digits):
    return int(''.join(map(str, digits)))

for p in itertools.permutations(range(10)):
    a = makenum(p[:5])
    b = makenum(p[5:])
    if a == 9 * b:
        print(a, b)

Answer 2

利用代数：

a / b = 9 == a = 9 * b

知道这一点，您只需要费心生成值：

[(9*num, num) for num in range(10000, 100000)]

如果你需要通过一些标准过滤掉东西，你可以很容易地写一个过滤函数：

def unique_numbers(num):
    num = str(num)
    return len(num) == len(set(num))

[(9*num, num) for num in range(10000, 100000) if unique_numbers(num) and unique_numbers(9*num)]

如果您想缩短一些时间，可以重新编写您的函数，使其 returns 成为有效对，否则 None。

def good_nums_or_none(num):
    a = num * 9
    b = num
    str_a = str(a)
    str_b = str(b)
    if len(a) == len(set(a)) and len(b) == len(set(b)):
         return a, b
    else:
         return None

[nums for nums in (good_nums_or_none(num) for num in range(10000, 100000)) if nums is not None]

或者，只需创建一个生成器并对其进行迭代：

 def target_numbers(factor=9, min=10000, max=100000):
     cur = min
     while cur < max:
         a = factor*cur
         b = cur
         str_a = str(a)
         str_b = str(b)
         if len(a) == len(set(a)) and len(b) == len(set(b)):
             yield a, b

 [num for num in target_numbers()]

如果你想在 b 中允许零填充数字，那么你可以使用这个过滤器：

def target_numbers(factor=9, min=1000, max=100000):
    cur = min                                      
    while cur < max:                               
        b = cur                                    
        a = factor*cur                             
        text = str(a) + str(b).zfill(5)            
        if len(text) == len(set(text)):            
            yield a, b                             
        cur += 1

Answer 3

运行 0.7 秒。比提到的大多数解决方案都快，尽管有点笨拙。

def sol(a,b,zero):
  for i in range(a,b):
     fl = 0
     marked = 10*[0]
     marked[0] = zero
     tmp = i
     while tmp > 0:
       marked[tmp%10] = marked[tmp%10] + 1
       tmp = tmp/10
     numerator = i*9

     while numerator > 0:
       marked[numerator%10] = marked[numerator%10] + 1
       numerator = numerator/10

     for j in range(10):
        if marked[j] != 1:
           fl = 1

     if fl == 0:
        print "found a solution ",i*9,"/",i


sol(1000,10000,1)
sol(10000,100000,0)

打印的解决方案是：

 found a solution  57429 / 6381
 found a solution  58239 / 6471
 found a solution  75249 / 8361
 found a solution  95742 / 10638
 found a solution  95823 / 10647
 found a solution  97524 / 10836

Answer 4

这是对@David 回答的细微变化。

如果我们看itertools.permutations([1,2,3,4])

>>> for p in itertools.permutations([1,2,3,4]):
...     print(p)
...
(1, 2, 3, 4)
(1, 2, 4, 3)
(1, 3, 2, 4)
(1, 3, 4, 2)
(1, 4, 2, 3)
(1, 4, 3, 2)
(2, 1, 3, 4)
(2, 1, 4, 3)
(2, 3, 1, 4)
(2, 3, 4, 1)
(2, 4, 1, 3)
(2, 4, 3, 1)
(3, 1, 2, 4)
(3, 1, 4, 2)
(3, 2, 1, 4)
(3, 2, 4, 1)
(3, 4, 1, 2)
(3, 4, 2, 1)
(4, 1, 2, 3)
(4, 1, 3, 2)
(4, 2, 1, 3)
(4, 2, 3, 1)
(4, 3, 1, 2)
(4, 3, 2, 1)

您会注意到对于元组 (a,b,c,d)，(c,d,a,b) 也会出现。如果数字 a == 9*b，则 b != a*9。我们将利用它来发挥我们的优势。

另外请注意，如果 a = 9*b，a 必须大于 b，除非我们使用负数或非整数。

您会看到，当我们查看结果时，将元组分成两半并将它们转换为数字，最初会给出一个较小的数字，然后是一个较大的数字。这是传递 permutations 排序列表的副作用。同样，我们可以利用这一点。

import itertools

def makenum(digits):
    return int(''.join(map(str, digits)))

for p in itertools.permutations(range(10)):
    first_half = makenum(p[:5])    
    second_half = makenum(p[5:])
    if second_half < first_half: # first half is smaller for first half of permutations, second half of permutations has been covered, backwards.
        break
    if second_half == 9 * first_half:
        print(first_half, second_half)

如果您正在接受用户输入，只需 sort 处理您的输入，您就应该能够获得相同的结果：

for p in itertools.permutations(sorted(digits)):
    # ...

Answer 5

采用 Wayne Werner 的解决方案，您可以这样做以添加数字唯一性约束（假设 Python 3）：

[(9*num, num) 
 for num in range(10000, 100000 // 9) 
 if len(set(str(num) + str(num * 9))) == 10]

这在我的机器上运行时间为 1.5 毫秒。

请注意，您只能检查 10000 到 100000 / 9 = 11111 之间的数字。

如果你想允许前面的零，你可以这样做：

[(9*num, num) 
 for num in range(0, 100000 // 9) 
 if len(set(("%05d" % num) + ("%05d" % (num * 9)))) == 10]

而这个需要 15 毫秒。

Python: 有策略地遍历十位数字 0-9

Python: Strategically go through ten digit numbers with 0-9

python

algorithm

python-3.x

digits