python - 在没有关于排序函数的先验知识的情况下合并 Python 中的有序列表

Question

我很难解决以下问题:我必须合并 N 个列表。每个列表都包含一些字符串对象。对于每个列表，虽然我不知道哪个是排序函数，但我知道它是有序的。此外，最终列表应尊重生成它的子项的所有顺序。例如:

l1 = ['This','world']
l2 = ['This','is','a','world','!']
l3 = ['a','hello','world']

merged_list = merge_function(l1,l2,l3)

我想要达到的结果是收到一个包含

merged_list # ['This','is','a','hello','world','!']

但我无法弄清楚如何做到这一点，因为除了提供元素的顺序之外，列表不遵循任何规则。任何帮助，将不胜感激。
编辑:我的问题的重点不是如何合并一些列表。问题是元素应该以一种尊重原始列表的所有顺序的方式合并。
所以我不能使用套装，因为它们有自己的订购政策。我想我必须坚持使用列表，因为它们更灵活，但我需要找到一种方法在最终列表中的正确位置插入新元素，因为我不能简单地附加它们。
例如:

l1 = ['This','world']
l2 = ['This','is','a','world','!']
merged_list = l1

如果我然后简单地将缺少的元素附加到 merge_list 我将获得:

merged_list # ['This','world','is','a','!']

这个列表打破了 l2 的顺序。我希望现在我能更好地解释这个问题。

Answer 1

您的问题的主要困难在于我们是否有这样的案例:

l1 = ['a', 'world']
l2 = ['This', 'is']
l3 = ['is', 'a']

在这种情况下，预期结果将是 ['This', 'is', 'a', 'world'] .虽然，关系 'This' < 'world'必须通过传递性获得。
这是一个解决方案，它通过使用定点算法生成完整的前辈表来确定您的排序。

def merge_function(*lists):
    predecessors = {w: set() for w in set(w for lst in lists for w in lst)}

    # Add trivial predecessors from the lists
    # For example in ['foo', 'bar', 'baz']:
    # we know 'foo' is a predecessor of 'baz'
    for l in lists:
        tail = l[::-1]
        for word in l:
            tail.pop()
            for successor in tail:
                predecessors[successor].add(word)

    # Use transitive property to update predecessor
    # This is the fixed point part of the algorithm
    change_occured = True
    while change_occured:
        change_occured = False
        for word, word_predecessors in predecessors.items():
            for predecessors_set in predecessors.values():
                if word in predecessors_set and any(w not in predecessors_set for w in word_predecessors):
                    change_occured = True
                    predecessors_set.update(word_predecessors)

    return sorted(predecessors, key=lambda w: predecessors[w])

l1 = ['a', 'world']
l2 = ['This', 'is']
l3 = ['is', 'a']

merged_list = merge_function(l1,l2,l3)

print(merged_list) # ['This', 'is', 'a', 'world']