我正在努力编写一个程序，将元组列表作为输入，并根据它们是否可以以某种方式排列返回一些东西。通常，我在编码之前知道如何解决问题，但在这种情况下，我很难想出一个好的方法。
这个想法是获取这样的输入列表。[(5， 2(， (3， 5(， (3， 3(， (1， 3(] 并验证是否可以以某种方式排列，使最后一个数字与下一个元组的开头匹配。所以在这种情况下是可能的，比如：[(1， 3(， (3， 3(， (3， 5(， (5， 2(]。所以它被验证为真实。元组也可以反转。
我正在考虑遍历列表并将有效的元组对组合在一起，但是如果它们没有以正确的方式分组以与其他对一起工作怎么办？此外，这可能太耗时了。
有什么想法吗？
谢谢！
如评论中所述，这相当于在元组元素图中找到哈密顿路径，元组之间的有向边与匹配的第一个和最后一个元素。虽然这是一个NP完全问题(哈密顿路径，我不知道用不同的方法来解决你的问题是否可以让它更容易(，但很容易为它想出蛮力算法。这是一个相当幼稚的递归实现：
def chained_list(lst):
# List of rearranged elements
chain = []
# Flags to tell whether each item has been picked already
picked = [False] * len(lst)
# Loop to add all possible first elements (so the recursive function
# can work on the assumption that there is a previous element)
for i, item in enumerate(lst):
# Add first element
chain.append(item)
# Mark as picked
picked[i] = True
# Attempt recursion
_chain_list_rec(lst, picked, chain)
# If we got a rearranged list finish
if len(chain) == len(lst):
return chain
# Otherwise remove the selected first element
picked[i] = False
chain.pop()
raise ValueError('cannot chain list')
def _chain_list_rec(lst, picked, chain):
# Take previous value to match
_, prev = chain[-1]
# Iterate through items
for i, (item, p) in enumerate(zip(lst, picked)):
# If item is available and matches previous value
if not p and item[0] == prev:
# Add it and mark it as picked
chain.append(item)
picked[i] = True
# Try remaining recursion
_chain_list_rec(lst, picked, chain)
# Check if we finished
if len(chain) == len(lst):
return
# Undo adding if not finished
picked[i] = False
chain.pop()
print(chained_list([(5, 2), (3, 5), (3, 3), (1, 3)]))
# [(1, 3), (3, 3), (3, 5), (5, 2)]
print(chained_list([(5, 2), (3, 3), (1, 3)]))
# ValueError: cannot chain list
您可以尝试以不同的方式改进它，例如使用多集而不是列表和picked标志列表(假设您想支持重复元素，否则set可以(，使用其他数据结构更快地搜索链中的下一个潜在项目(例如，一个带有键的第一个元素的字典，并值以该元素开头的多组元组(， 或添加完成检查(在递归开始时检查len(chain) == len(lst)以在最后一步中保存循环(。您还可以在递归的每一步检查当前部分解决方案的可行性。请注意，对于任何偏解：a( 必须至少有一个以prev开头的项目(chain中最后一项的第二个值( b( 对于任何给定的值k，以k开头的可用元组的数量通常必须等于以k结尾的可用元组的数量， 调整k == prev并注意最多可以有一个k有一个额外的元组完成k(这将是最后一个(。如果这些条件不成立，那么该递归路径是不可行的。您可能会想到其他方法来提高效率。但是，无论如何，在某个点或另一个点执行该算法将变得不可能昂贵，因此请记住，此方法仅适用于相对较小的输入。