主页 / coding / 问题 / 79587366
Accepted
rasputin
Asked: 2025-04-23 04:03:04 +0800 CST

创建未知真实顺序的列表的有序并集的有效算法

  • 772

我有一堆需要合并的列表。每个列表都有一个排序，并且每个排序都与原始列表的排序一致。（所谓“一致”，是指每个列表都可以通过从原始列表中删除项目来重现，而无需重新排列任何项目。）

我的问题是我没有原始列表，我必须使用我拥有的部分列表尽可能地复制它。

例如，考虑以下有序列表：

a = ["first", "fourth", "fifth", "sixth", "eighth", "sophomore", "junior"]
b = ["second", "third", "fourth", "sixth", "seventh", "eighth", "freshman", "sophomore", "senior"]
c = ["first", "second", "freshman", "sophomore", "junior", "senior"]
...
partial_lists = [a, b, c, ...]

从这三个列表中，可以恢复原始列表。然而，在某些情况下，这可能行不通。无论如何，我希望创建一个列表，merged_list使其能够保留每个部分列表的顺序。（也就是说，理论上，任何指定的部分列表都可以仅通过操作merged_list来重建。）可以安全地假设每个部分列表不包含重复项，并且也必须不包含任何重复项。merged_listmerged_list.remove()merged_list

对于这个例子，merged_list将是["first", "second", "third", "fourth", "fifth", "sixth", "seventh", "eighth", "freshman", "sophomore", "junior", "senior"]

是否存在一种有效的算法可以处理任意数量的部分列表？

algorithm

1 个回答

  1. Best Answer

    这是关于拓扑排序，给定一些依赖关系。

    有几种方法可以找到拓扑排序的原始列表。这将有助于构建一个图数据结构，其中包含所有以节点为键的依赖项。然后，生成没有任何前任的节点，并将其从图中删除。这将产生一组没有任何前任的新节点，等等。

    以下是 Python 中的实现：

    from collections import defaultdict

def topological_sort(lists):
    # create graph (pred + succ)
    succ = defaultdict(set)
    pred = defaultdict(set)
    nodes = set()
    for lst in lists:
        nodes.update(lst)
        for a, b in zip(lst, lst[1:]):
            succ[a].add(b)
            pred[b].add(a)
        
    # get nodes that don't have a predecessor
    first = { node for node in nodes if not pred[node] }

    while first:
        collect = list(first)
        first.clear()
        yield from collect  # yield the nodes that don't have a predecessor (anymore)
        for a in collect:
            for b in succ[a]:
                pred[b].remove(a) # those can't be a predecessor anymore
                if not pred[b]: # this may make another node to be without predecessor
                    first.add(b)
    
        
# demo run:
a = ["first", "fourth", "fifth", "sixth", "eighth", "sophomore", "junior"]
b = ["second", "third", "fourth", "sixth", "seventh", "eighth", "freshman", "sophomore", "senior"]
c = ["first", "second", "freshman", "sophomore", "junior", "senior"]
partial_lists = [a, b, c]
result = list(topological_sort(partial_lists))

    对于此示例运行，result将出现如下结果：

    ['first', 'second', 'third', 'fourth', 'fifth', 'sixth', 'seventh', 'eighth', 'freshman', 'sophomore', 'junior', 'senior']
    • 3

相关问题