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

Question

我正在编写一个程序，以将元组列表作为输入，并根据它们是否可以以某种方式排列来返回一些内容。通常我在编码之前就知道如何解决问题，但在这种情况下，我很难想出一个好的方法来解决这个问题。
这个想法是输入一个这样的列表.. [(5, 2), (3, 5), (3, 3), (1, 3)] 并验证是否可以以某种方式排列，以便最后number 匹配下一个元组的开头。所以在这种情况下是可能的，比如:[(1, 3), (3, 3), (3, 5), (5, 2)]。于是验证为真。元组也可以颠倒。
我想遍历列表并将有效的元组对组合在一起，但是如果它们没有以正确的方式分组以与其余的对一起工作怎么办？也可能太费时间了。
有任何想法吗？
谢谢!

Answer 1

正如评论中提到的，这相当于找到一个 Hamiltonian path在元组元素的图中，元组之间的有向边与匹配的第一个和最后一个元素。虽然它是一个 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

您可以尝试以不同的方式改进它，例如使用 multiset而不是列表和 picked标志列表(假设您想支持重复元素，否则 set 可以)，使用其他数据结构更快地搜索链中的下一个潜在项目(例如，一个 dict 以第一个元素为键并为多集赋值以该元素开头的元组)，或添加完成检查(在递归开始时检查 len(chain) == len(lst) 以保存最后一步的循环)。您还可以在递归的每一步检查当前部分解决方案的可行性。请注意，对于任何部分解决方案: a) 必须至少有一项以 prev 开头(chain 中最后一项的第二个值) b) 对于任何给定的值 k ，以 k 开头的可用元组数通常必须等于以 k 结尾的可用元组的数量，调整为 k == prev并注意最多可以有一个 k其中有一个额外的元组以 k 结束(这将是最后一个)。如果这些条件不成立，那么该递归路径是不可行的。您可能会想到其他方法来提高效率。然而，在任何情况下，算法在某一点或另一点执行都将变得非常昂贵，因此请记住，这种方法仅适用于相对较小的输入。