时间戳

首页 > 解决方案 > 对列表列表进行逻辑排序（部分有序集 -> 拓扑排序）

python - 对列表列表进行逻辑排序（部分有序集 -> 拓扑排序）

问题描述

编辑 接受的答案适用于满足严格偏序集要求的集合，因此可以构造有向无环图：

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

子列表之间的整体顺序是一致的，这意味着不会有像这样的子列表：['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技巧可以提高效率？

标签： python

解决方案

您可以创建一个查找函数来确定是否应将特定值放在另一个值之前或之后：

d = [['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd']]
flattened = {i for b in d for i in b}
def _lookup(a, b):
  _loc = [i for i in d if a in i and b in i]
  return True if not _loc else _loc[0].index(a) < _loc[0].index(b)

class T: 
  def __init__(self, _val):
    self.v = _val
  def __lt__(self, _n):
    return _lookup(self.v, _n.v)

final_result = [i.v for i in sorted(map(T, flattened))]

输出：

['b', 'a', 'c', 'd']

使用[['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd'], ['a', 'e']]：

['b', 'a', 'c', 'e', 'd']

推荐阅读