python - 按层次顺序按降序百分比对元组列表进行排序

Question

我正在尝试按主导顺序对具有多个级别的成分声明进行排序(按百分比降序)。

我正在使用Python，并且有一个元组列表，每个元组都有以下变量:(成分、百分比、childID、parentID)。

它来自看起来有点像这样的数据，数据可以按任何顺序输入。下面的列是成分/子成分、百分比、childID、parentID。

#Ing1   30%             1   0
#---Sub1    30%         2   1
#---Sub2    60%         3   1
#------Sub3     15%     4   3
#------Sub4     85%     5   3
#---Sub5    10%         6   1
#Ing2   10%             7   0
#Ing3   60%             5   0

我现有的代码在一个类似这样的列表中将其输出给我(输入的顺序):

list = [(Ing1,30,1,0),(Sub1,30,2,1),(Sub2,60,3,1),(Sub3,15,4,3),(Sub4,85,5,3),(Sub5,10,6,1),(Ing2,10,7,0),(Ing3,60,5,0)]

我需要做的是按购买百分比降序排列此列表，同时保持从较低级别到上层的层次结构完整。因此，首先是第 3 级成分(Sub3、Sub4)，然后是下一个级别，然后是顶层。
子级别需要与其父级别一起排序。

因此，对于上面的示例，我需要按以下顺序输出:

> #Ing3 60%             5   0
> #Ing1 30%             1   0
> #---Sub2  60%         3   1
> #------Sub4   85%     5   3
> #------Sub3   15%     4   3
> #---Sub1  30%         2   1
> #---Sub5  10%         6   1
> #Ing2 10%             7   0

所以列表应该如下所示:

list = [(Ing3,60,5,0),(Ing1,30,1,0),(Sub2,60,3,1),(Sub4,85,5,3),(Sub3,15,4,3),(Sub1,30,2,1),(Sub5,10,6,1),(Ing2,10,7,0)]

在 Python 中执行此操作最优雅的方法是什么？哦，还有一个警告，因为我可以导入的模块受到限制。如果它不是包含的模块，由于我的环境，我可能无法访问它。

Answer 1

你可以使用这样的生成器:

lst = [('Ing1',30,1,0),
       ('Sub1',30,2,1),
       ('Sub2',60,3,1),
       ('Sub3',15,4,3),
       ('Sub4',85,5,3),
       ('Sub5',10,6,1),
       ('Ing2',10,7,0),
       ('Ing3',60,5,0)]

def sort_hierarchical(lst, parent=0):
    # sort the current layer (excluding all other elements) by the second element
    res = sorted([i for i in lst if i[3] == parent], key=lambda x: x[1], reverse=True)
    for item in res:
        yield item
        # recurse for all childs of this item
        for subitem in sort_hierarchical(lst, parent=item[2]):
            yield subitem

>>> list(sort_hierarchical(lst))
[('Ing3', 60, 5, 0),
 ('Ing1', 30, 1, 0),
 ('Sub2', 60, 3, 1),
 ('Sub4', 85, 5, 3),
 ('Sub3', 15, 4, 3),
 ('Sub1', 30, 2, 1),
 ('Sub5', 10, 6, 1),
 ('Ing2', 10, 7, 0)]

如果在将列表传递给函数之前仅对列表进行一次排序，则可以进一步简化。然后你只需要过滤项目而不需要多次排序:

def return_hierarchical(lst, parent=0):
    for item in (i for i in lst if i[3] == parent):
        yield item
        for subitem in return_hierarchical(lst, parent=item[2]):
            yield subitem

>>> list(return_hierarchical(sorted(lst, key=lambda x: x[1], reverse=True)))
[('Ing3', 60, 5, 0),
 ('Ing1', 30, 1, 0),
 ('Sub2', 60, 3, 1),
 ('Sub4', 85, 5, 3),
 ('Sub3', 15, 4, 3),
 ('Sub1', 30, 2, 1),
 ('Sub5', 10, 6, 1),
 ('Ing2', 10, 7, 0)]

在 Python-3.3+ 中，您可以使用 yield from并使其更短:

def return_hierarchical(lst, parent=0):
    for item in (i for i in lst if i[3] == parent):
        yield item
        yield from return_hierarchical(lst, parent=item[2])

一般说明:

我将您的 list 重命名为 lst，这样它就不会遮盖内置的 list .

您正在处理元组，但您通过名称引用它们，因此您也可以使用 collections.namedtuple 。这还允许您按属性引用项目:

from collections import namedtuple

ingredient = namedtuple('Ingredient', ['ingredient', 'percentage', 'order', 'parent'])

lst = [ingredient('Ing1',30,1,0), ingredient('Sub1',30,2,1), ingredient('Sub2',60,3,1),
       ingredient('Sub3',15,4,3), ingredient('Sub4',85,5,3), ingredient('Sub5',10,6,1),
       ingredient('Ing2',10,7,0), ingredient('Ing3',60,5,0)]

def return_hierarchical(lst, parent=0):
    for item in (i for i in lst if i.parent == parent):
        yield item
        yield from return_hierarchical(lst, parent=item.parent)

list(sort_hierarchical(sorted(lst, key=lambda x: x.percentage, reverse=True)))

就我个人而言，我喜欢 namedtuple ，但有些不喜欢，你说你受到导入的限制(它在标准库中，但尽管如此)，所以我只将它包含在这里......在结束。