在Python中检查唯一输出

Question

我昨天遇到了一个有趣的数学问题，已经解决了。不过我写的代码在运行的时候需要手动中断，不然它会一直跑下去，哈哈。所以我改了一下，让它有个结束条件，但现在它只打印出一个解就停了。

这个问题是这样的：“你有数字123456789，按这个顺序排列。在每个数字之间，你必须插入什么都不插、加号或者乘号，使得最终的表达式等于2002。写一个程序，打印出所有的解。（一共有两个。）”

import random


def try1(param):
    global solved
    opers = ['+', '*', '']
    hotpotato = ('%s'.join(param) % (random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     )
             )
    if eval(hotpotato) == 2002:
        solved += 1
        print "Solution:", hotpotato, "= 2002     :-)"

    else:
        pass


solved = 0
while solved == 0:
    try1('123456789')

这段代码只打印出它找到的第一个解就停了。有没有人能告诉我怎么才能让它在停之前打印出两个解呢？

Answer 1

解决你问题的方法是，当解决方案数量等于2时就停止。

不过，你代码的真正问题在于使用了随机数。在算法中使用随机数通常不是个好主意，因为这样可能导致你的代码运行上百年。

其实有一种更简单、更快的方法，可以使用itertools库：

import itertools

for s in itertools.product(("+", "*", ""), repeat=8):
    z = itertools.izip_longest("123456789", s, fillvalue="")
    e = "".join(itertools.chain.from_iterable(z))

    if eval(e) == 2002:
        print(e)

当找到两个解决方案时，其实不需要停止，因为你的代码已经在0.2秒内完成了 :).

Answer 2

别用随机的方法，应该把所有可能的运算符组合都列出来（当然，如果前几个数字的结果已经大于2002，那后面的结果就不可能小于2002，这样可以减少一些搜索的范围）。itertools 是个好帮手。

如果你这样做，你的程序会很快完成。

如果你知道恰好有两个解，你可以从 try1 返回一个解，然后继续循环直到找到两个不同的解，不过这样做其实不太优雅，对吧？

Answer 3

把你的解决方案存放在一个集合里：

solutions = set([])

每次找到一个解决方案，就更新这个集合：

solutions.append(solution)

集合的好处是它不会存储重复的内容：

>>> len(set([1, 1, 1, 1, 1, 1, 1]))
1

所以只需要循环，直到集合的大小大于一：

while len(solved) < 2:
    try1('123456789')

---

另外，你可以把这段代码简化：

hotpotato = ('%s'.join(param) % (random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 )
         )

变成这样：

hotpotato = ('%s'.join(param) % (random.choice(opers) for i in range(8))))