逻辑排序列表列表(部分有序集 - >拓扑排序)

Question

编辑 接受的答案适用于满足严格部分有序集的要求的集合,以便可以构造有向非循环图:

• irreflexivity not a < a:列表不包含像['a','a']
• 传递性if a < b and b < c then a < c:列表不包含像['a','b'],['b','c'],['c','a']
• 不对称if a < b then not b < a:列表不包含像['a','b'],['b','a']

---

获取此列表列表:
[['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd'], ]
并将其展平为单个列表,根据值的邻居进行排序:

• 第一个子列表告诉你b在c之前
• 然后是前一个c
• b之前
• 最后是在c之后

子列表之间的整体排序是一致的,这意味着不会有像这样的子列表:['b','c'],['c','b'].所以结果应该是:['b', 'a', 'c', 'd']

经过一段很长的时间,我想出了这个丑陋的混乱:

def get_order(_list):
    order = _list[0]
    for sublist in _list[1:]:
        if not sublist:
            continue
        if len(sublist) == 1:
            if sublist[0] not in order:
                order.append(sublist[0])
            continue
        new_order = order.copy()
        for index, value in enumerate(sublist):
            inserted = False
            new_order_index = None
            if value in new_order:
                new_order_index = new_order.index(value)
                new_order.remove(value)
            for previous_value in sublist[:index][::-1]:
                if previous_value in new_order:
                    insert_index = new_order.index(previous_value) + 1
                    print('inserting', value, 'at position', insert_index, 'after', previous_value)
                    new_order.insert(insert_index, value)
                    inserted = True
                    break
            if inserted:
                continue
            for next_value in sublist[index:]:
                if next_value in new_order:
                    insert_index = new_order.index(next_value)
                    print('inserting', value, 'at position', insert_index, 'before', next_value)
                    new_order.insert(insert_index, value)
                    inserted = True
                    break
            if inserted:
                continue
            if new_order_index is None:
                print('appending', value)
                new_order.append(value)
            else:
                print('leaving', value, 'at position', new_order_index)
                new_order.insert(new_order_index, value)
        order = new_order
    return order

if __name__ == '__main__':
    test_list = [['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd'], ]
    order = get_order(test_list)
    #>>> inserting a at position 1 before c
    #>>> inserting c at position 2 after a
    #>>> inserting d at position 3 after c
    #>>> inserting a at position 1 before c
    #>>> inserting c at position 2 after a
    #>>> inserting b at position 0 before a
    #>>> inserting a at position 1 after b
    print(order)
    #>>> ['b', 'a', 'c', 'd']

它似乎完全符合预期,但它远没有效率(或者说优雅).
有没有可以这样排序的算法？
或者是否有一些pythonic技巧可以提高效率？

---

Answer 1

nosklo 和 Ajax1234 的现有答案都在[[1, 3], [3, 5], [5, 2], [2, 4]]. 您问题中的尝试在输入 时失败[[1, 4], [2, 3], [3, 4], [1, 2]]。

正确的方法如 BowlingHawk95 所描述的：对由输入列表导出的有向无环图执行拓扑排序。

我们可以实现自己的拓扑排序，但让现有的图形库处理它更安全。例如，网络X：

from itertools import chain, tee

import networkx
import networkx.algorithms

# pairwise recipe from the itertools docs.
def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def merge_ordering(sublists):
    # Make an iterator of graph edges for the new graph. Some edges may be repeated.
    # That's fine. NetworkX will ignore duplicates.
    edges = chain.from_iterable(map(pairwise, sublists))

    graph = networkx.DiGraph(edges)
    return list(networkx.algorithms.topological_sort(graph))

这会为问题中的输入、[[1, 3], [3, 5], [5, 2], [2, 4]]其他答案失败的情况以及[[1, 4], [2, 3], [3, 4], [1, 2]]您的尝试失败的情况生成正确的输出：

>>> merge_ordering([[1, 3], [3, 5], [5, 2], [2, 4]])
[1, 3, 5, 2, 4]
>>> merge_ordering([['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd']])
['b', 'a', 'c', 'd']
>>> merge_ordering([[1, 4], [2, 3], [3, 4], [1, 2]])
[1, 2, 3, 4]

如果输入列表不能唯一确定展平形式，我们还可以编写一个引发错误的版本：

def merge_ordering_unique(sublists):
    # Make an iterator of graph edges for the new graph. Some edges may be repeated.
    # That's fine. NetworkX will ignore duplicates.
    edges = chain.from_iterable(map(pairwise, sublists))

    graph = networkx.DiGraph(edges)
    merged = list(networkx.algorithms.topological_sort(graph))

    for a, b in pairwise(merged):
        if not graph.has_edge(a, b):
            raise ValueError('Input has multiple possible topological orderings.')

    return merged

演示：

>>> merge_ordering_unique([['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd']])
['b', 'a', 'c', 'd']
>>> merge_ordering_unique([[1, 3, 4], [1, 2, 4]])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 11, in merge_ordering_unique
ValueError: Input has multiple possible topological orderings.