这是我为解决这个问题而编写的一个快速程序。这可能不是解决此问题的最有效方法，但它可以完成工作。
l = [(1,2),(2,3),(3,4),(4,5)] # replace with whatever your full list is
import itertools
for perm in itertools.permutations(l,len(l) / 2):
pair_list = []
for pair in perm:
if pair[0] in itertools.chain(*(i for i in pair_list)) \
or pair[1] in itertools.chain(*(i for i in pair_list)):
break
pair_list.append(pair)
if len(pair_list) == len(l) / 2:
unused = []
for n in itertools.chain(*(i for i in l)):
if n not in itertools.chain(*(i for i in pair_list)) and n not in unused:
unused.append(n)
print pair_list,'unused:',unused
另外，您确定要识别所有排列吗？要获得您的确切输出，我需要替换itertools.permutations为itertools.combinations.
这是我使用的输出itertools.permutations：
[(1, 2), (3, 4)] unused: [5]
[(1, 2), (4, 5)] unused: [3]
[(2, 3), (4, 5)] unused: [1]
[(3, 4), (1, 2)] unused: [5]
[(4, 5), (1, 2)] unused: [3]
[(4, 5), (2, 3)] unused: [1]
而我使用的是itertools.combinations：
[(1, 2), (3, 4)] unused: [5]
[(1, 2), (4, 5)] unused: [3]
[(2, 3), (4, 5)] unused: [1]
编辑： 好的，这个新版本变得更难了。我现在要做的是在较大的列表中找到所有子组，其中这些对都彼此相邻。我找到每个子组的组合，然后将它们全部放回一起，itertools.product最后加上一个。此外，在我的测试用例中，我在末尾添加了一个额外的对 (8,9) 以确保一切都适用于多个组。这是代码：
l = [(1,2),(2,3),(3,4),(4,5),(7,8),(8,9)]
import itertools,math
## Create sublists for each set of adjacent pairs
l.sort(lambda x,y:cmp(x[0],y[0]))
newl = []
subl = []
for i in range(len(l)):
if subl == []:
subl.append(l[i])
else:
if l[i][0] == subl[-1][1]:
subl.append(l[i])
else:
newl.append(subl)
subl = [l[i]]
newl.append(subl)
pair_lists = []
## Find all combinations for each sublist
for subl in newl:
cur_pair_list = []
for perm in itertools.combinations(subl,int(math.ceil(len(subl) / 2.0))):
pair_list = []
for pair in perm:
if pair[0] in itertools.chain(*pair_list) \
or pair[1] in itertools.chain(*pair_list):
break
pair_list.append(pair)
if len(pair_list) == int(math.ceil(len(subl) / 2.0)):
cur_pair_list.append(pair_list)
pair_lists.append(cur_pair_list)
## Combine combinations for each sublist and determine unused for each combination
final_list = list(list(itertools.chain(*i)) for i in itertools.product(*pair_lists))
for subl in final_list:
unused = []
for n in itertools.chain(*l):
if n not in itertools.chain(*subl) and n not in unused:
unused.append(n)
print subl,'unused:',unused
这是输出：
[(1, 2), (3, 4), (7, 8)] unused: [5, 9]
[(1, 2), (3, 4), (8, 9)] unused: [5, 7]
[(1, 2), (4, 5), (7, 8)] unused: [3, 9]
[(1, 2), (4, 5), (8, 9)] unused: [3, 7]
[(2, 3), (4, 5), (7, 8)] unused: [1, 9]
[(2, 3), (4, 5), (8, 9)] unused: [1, 7]
编辑#2：
所以在这里，我唯一要做的就是改变列表的排序方式。注释下方的所有代码## Find all combinations for each sublist都可以保持不变。
这是该注释上方的新代码：
l = [(427, 3434), (614, 2445), (840, 614), (910, 3939), (1065, 4314), (1347, 2616), (2445, 427), (2616, 3901), (2749, 1065), (3403, 910), (3434, 1347), (3659, 1411), (3901, 3684), (3939, 2638), (4203, 3403), (4314, 840)]
import itertools,math
def sort(l):
l = list(l)
newl = []
subl = []
i = l[0]
while len(l) > 0:
subl.append(i)
l.remove(i)
k = None
for j in l:
if j[0] == i[1]:
k = j
break
if k:
i = k
else:
newl.append(subl)
subl = []
if len(l) > 0:
i = l[0]
i = 0
while i < len(newl):
j = 0
while j < len(newl):
if newl[j][-1][1] == newl[i][0][0]:
for k in newl[j][::-1]:
newl[i].insert(0,k)
newl.pop(j)
continue
j += 1
i += 1
return newl
pair_lists = []
newl = sort(l)
这是我在你的新列表上运行它时得到的输出：
[(2749, 1065), (4314, 840), (614, 2445), (427, 3434), (1347, 2616), (3901, 3684), (4203, 3403), (910, 3939), (3659, 1411)] unused: [2638]
[(2749, 1065), (4314, 840), (614, 2445), (427, 3434), (1347, 2616), (3901, 3684), (4203, 3403), (3939, 2638), (3659, 1411)] unused: [910]
[(2749, 1065), (4314, 840), (614, 2445), (427, 3434), (1347, 2616), (3901, 3684), (3403, 910), (3939, 2638), (3659, 1411)] unused: [4203]