不理解使用itertools.permutations（）获得的结果

Question

这是代表在12空间中从0到15的一组不同数字的代码，使得一些相邻数字之间的差异也是不同的。

import itertools

list = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

for i in itertools.permutations(list,12):
    a1 = abs(i[0] - i[1])
    b1 = abs(i[0] - i[2])
    a = abs(i[0] - i[3])
    b = abs(i[0] - i[4])
    c = abs(i[0] - i[5])
    d = abs(i[1] - i[6])
    e = abs(i[2] - i[7])
    f = abs(i[3] - i[8])
    g = abs(i[4] - i[9])
    h = abs(i[5] - i[10])
    g1 = abs(i[6] - i[11])
    h1 = abs(i[7] - i[11])
    c1 = abs(i[8] - i[11])
    d1 = abs(i[9] - i[11])
    e1 = abs(i[10] - i[11])
    L= [a1, b1, a, b, c, d, e, f, g, h, g1, h1, c1, d1, e1]
    if (len(set(L))==15):
        print(i)
        print(L)

这段代码似乎没有输出，但我无法弄清楚原因。

Answer 1

这是一种生成随机解决方案的方法。它将所有变量检查移动到一个循环中，并在发生冲突时使循环短路：

import itertools, random

labels = list(range(16))
edges = ((0,1),(0,2),(0,3),(0,4),(0,5),(1,6),(2,7),(3,8),(4,9),(5,10),(6,11),(7,11),(8,11),(9,11),(10,11))
num_vertices = 12

def solve(labels,edges,num_vertices):
    shuffled_labels = labels[:] #make a copy
    random.shuffle(shuffled_labels)
    for p in itertools.permutations(shuffled_labels,num_vertices):
        differences = [0]*16
        solved = True #innocent until proven guilty
        for i,j in edges:
            difference = abs(p[i]-p[j])
            differences[difference] += 1
            if differences[difference] == 2:
                solved = False
                break #no need to check more edges
        if solved:
            return p

一次运行（约1分钟）：

>>> solve(labels,edges,num_vertices)
(6, 5, 1, 14, 3, 2, 11, 15, 12, 13, 9, 0)

这很容易验证，以满足您的约束。

这是一个生成器解决方案，它将产生所有可能的解决方

def solutions(labels,edges,num_vertices):
    for p in itertools.permutations(labels,num_vertices):
        differences = [0]*16
        solved = True #innocent until proven guilty
        for i,j in edges:
            difference = abs(p[i]-p[j])
            differences[difference] += 1
            if differences[difference] == 2:
                solved = False
                break #no need to check more edges
        if solved:
            yield p

像例如：

for p in solutions(labels,edges,num_vertices): print(p)

与通常在不到一分钟内返回的随机方法不同，发生器在开始产生结果之前会搅拌很长时间。这表明身份置换（这个发生器开始的地方）远非一个解决方案。尽管如此，它最终会产生排列（大约10-15分钟后），第一个是：

(0, 1, 3, 13, 14, 15, 10, 7, 6, 2, 4, 12)

（同意@jasonharper的结果）。