这些元组可以以某种方式排列吗？

Question

我正在编写一个程序，以将元组列表作为输入，并根据它们是否可以以某种方式排列来返回一些内容。通常我在编码之前就知道如何解决问题，但在这种情况下，我很难想出一个好的方法来解决这个问题。

这个想法是输入一个这样的列表.. [(5, 2), (3, 5), (3, 3), (1, 3)] 并验证是否可以以某种方式排列，以便最后number 匹配下一个元组的开头。所以在这种情况下是可能的，比如：[(1, 3), (3, 3), (3, 5), (5, 2)]。于是验证为真。元组也可以颠倒。

我想遍历列表并将有效的元组对组合在一起，但是如果它们没有以正确的方式分组以与其余的对一起工作怎么办？也可能太费时间了。

有任何想法吗？

谢谢！

Answer 1

正如评论中提到的，这相当于在元组元素图中查找哈密顿路径，该元组元素之间具有匹配第一个和最后一个元素的元组之间的有向边。虽然这是一个 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标志列表（假设您想支持重复元素，否则 aset可以做到），使用其他数据结构更快地搜索下一个链中的潜在项目（例如，字典的键是第一个元素，值是从该元素开始的元组的多重集），或添加完成检查（len(chain) == len(lst)在递归开始时检查以在最后一步中保存循环）。您还可以在递归的每一步检查当前部分解决方案的可行性。请注意，对于任何部分解决方案： a) 必须至少有一个以prev( 中最后一项的第二个值chain) 开头的项 b) 对于任何给定值k，以 开头的可用元组的数量k通常必须等于以 结尾的可用元组的数量k，调整k == prev并注意最多可以有一个k以 结尾的额外元组k（这将是最后一个）。如果这些条件不成立，则该递归路径不可行。您可能会想到其他方法来提高效率。然而，无论如何，该算法在某一点或另一点执行起来都会变得极其昂贵，因此请记住，这种方法仅适用于相对较小的输入。