python - 代码花费太多时间

Question

我在接受用户输入后编写代码来排列数字。排序要求相邻数之和为质数。直到 10 作为输入代码工作正常。如果我超出这个范围，系统就会挂起。请告诉我优化它的步骤

前输入 8
答案应该是:(1, 2, 3, 4, 7, 6, 5, 8)
代码如下....

import itertools

x = raw_input("please enter a number")
range_x = range(int(x)+1)
del range_x[0]
result = list(itertools.permutations(range_x))
def prime(x):
    for i in xrange(1,x,2):
        if i == 1:
            i = i+1
        if x%i==0 and i < x :
            return False
    else:
        return True

def is_prime(a):
    for i in xrange(len(a)):
        print a
        if i < len(a)-1:
            if prime(a[i]+a[i+1]):
                pass
            else:
                return False
        else:
            return True


for i in xrange(len(result)):
    if i < len(result)-1:
        if is_prime(result[i]):
            print 'result is:'
            print result[i]
            break
    else:
        print 'result is'
        print result[i-1]

Answer 1

为了后代 ;-)，这里还有一个基于寻找哈密顿路径的方法。这是 Python3 代码。如所写，它在找到第一条路径后停止，但可以轻松更改以生成所有路径。在我的盒子上，它在大约一分钟的时间内为从 1 到 900 的所有 n 找到了解决方案。对于略大于 900 的 n，它超过了最大递归深度。

素数生成器 (psieve()) 对于这个特定问题来说太过分了，但我手头有它，不想再写一个 ;-)

路径查找器 (ham()) 是一个递归回溯搜索，使用经常(但不总是)非常有效的启发式排序:所有相邻的顶点到目前为止路径中的最后一个顶点，首先查看剩余导出最少的顶点。例如，这是应用于解决 Knights Tour 问题的“通常”启发式方法。在这种情况下，它通常会找到一条根本不需要回溯的路线。你的问题似乎比那更难一些。

def psieve():
    import itertools
    yield from (2, 3, 5, 7)
    D = {}
    ps = psieve()
    next(ps)
    p = next(ps)
    assert p == 3
    psq = p*p
    for i in itertools.count(9, 2):
        if i in D:      # composite
            step = D.pop(i)
        elif i < psq:   # prime
            yield i
            continue
        else:           # composite, = p*p
            assert i == psq
            step = 2*p
            p = next(ps)
            psq = p*p
        i += step
        while i in D:
            i += step
        D[i] = step

def build_graph(n):
    primes = set()
    for p in psieve():
        if p > 2*n:
            break
        else:
            primes.add(p)

    np1 = n+1
    adj = [set() for i in range(np1)]
    for i in range(1, np1):
        for j in range(i+1, np1):
            if i+j in primes:
                adj[i].add(j)
                adj[j].add(i)
    return set(range(1, np1)), adj

def ham(nodes, adj):
    class EarlyExit(Exception):
        pass

    def inner(index):
        if index == n:
            raise EarlyExit
        avail = adj[result[index-1]] if index else nodes
        for i in sorted(avail, key=lambda j: len(adj[j])):
            # Remove vertex i from the graph.  If this isolates
            # more than 1 vertex, no path is possible.
            result[index] = i
            nodes.remove(i)
            nisolated = 0
            for j in adj[i]:
                adj[j].remove(i)
                if not adj[j]:
                    nisolated += 1
                    if nisolated > 1:
                        break
            if nisolated < 2:
                inner(index + 1)
            nodes.add(i)
            for j in adj[i]:
                adj[j].add(i)

    n = len(nodes)
    result = [None] * n
    try:
        inner(0)
    except EarlyExit:
        return result

def solve(n):
    nodes, adj = build_graph(n)
    return ham(nodes, adj)