0

我想找到解决方案Spoiler alert Euler #41 problem。我问的问题是它的子问题。我有问题的解决方案，但问题在于解决方案。这是我正在检查的实际内容：-

large = 0
x = ''

for i in range(1,10):
x += '%d' %i
for perm in permutations(x):
    if(isPrime(int(perm))):
        large = perm

print large

这是排列函数：-

def permutations(val):
    res = []
    if len(val) == 1:
        res = [val]
    else:
        for i, c in enumerate(val):
            for perm in permutations(val[:i]+val[i+1:]):
                res += [c+perm]

return res

上面的程序在从 1 到 987654321 的排列中找到所有素数的排列。

但问题是large = 7652413 之后，large 没有进一步增长。程序在大约 3 秒内达到此值，但程序在大约 4 分钟内完成。所以我想知道是否有任何方法可以节省时间。

这个问题也可以概括为一种查找函数是否告诉您该函数是否花费太长时间才能获得所需结果的方法。

4

2 回答 2

2

只回答手头的直接问题，您可以通过使用itertools.permutations.

但是，从数学上讲，你可以通过意识到你想要的素数最多有 7 位来减少你的问题。如果它有 8，那么1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36，它可以被 3 整除，因此不能是素数。加 9 得到 45，它也能被 3 整除。

于 2013-07-09T21:53:57.833 回答
1

听起来您正在寻找一种方法来应用超时作为启发式方法来告诉您“可能完成”并停止工作。

最简单的方法是在开始时或每次递增时获取当前时间large（取决于您认为相关的时间），然后每隔一段时间检查一次之后的时间，如果超过则取消。

如果在您的代码中手动“每隔一段时间检查一次”不合理，您可以使用后台线程来执行此操作，但让我们保持简单，因为这里似乎没有必要这样做。

所以：

class Timeout(object):
    def __init__(self, timeout_seconds):
        self.timeout = datetime.timedelta(0, timeout_seconds)
        self.reset()
    def reset(self):
        self.start = datetime.datetime.now()
        self.stop = self.start + self.timeout
    def check(self):
        if datetime.datetime.now() > self.stop:
            raise Exception('Timeout!')

现在，您可以这样做：

t = Timeout(30)
for perm in permutations(x):
    if isPrime(int(perm)):
        large = perm
        t.reset()
    t.check()

如果您想使用自更新以来的循环数而不是秒数，或者使用一些更高级的启发式方法，那么它就不再复杂了。您只需要描述启发式，然后将其转换为代码。

于 2013-07-09T21:52:58.347 回答