如何根据嵌套列表中的每个元素对嵌套列表进行排序

Question

我有一个模型页面，它存储一个可选的父页面（它本身的实例）。在我看来，我创建了一个函数，它将 return 所有页面及其父页面的嵌套列表。

比如我的页面架构是

CCC
  AAA
    DDD
    KKK
      EEE
ZZZ
  BBB

所以 DDD 有父页面 AAA，它有自己的父页面 CCC。 CCC 是首页，没有父页。

该函数将首先获取所有页面实例的查询集，并按字母顺序对它们进行排序。然后它将继续递归地生成一个 "full parent architecture" 列表，其中该列表中的每个元素都是所有父页面的另一个列表，包括页面本身。从上面的示例中，如果我们为页面 DDD 获取列表的一部分，它将 return [CCC, AAA, DDD].

我的函数目前 return 是一个与上述示例类似的列表：

[ 
  [CCC, AAA],
  [ZZZ, BBB],
  [CCC],
  [CCC, AAA, DDD],
  [CCC, AAA, KKK, EEE],
  [CCC, AAA, KKK],
  [ZZZ],
]

正如您从该列表中看到的那样，所有元素都根据该列表中的最后一个元素按字母顺序排序。现在我想在我的前端显示所有这些父页面，基本上看起来像一个站点地图，并显示我网站上所有页面的正确父架构，这些页面根据每个嵌套列表中的每个元素按字母顺序排序。最终结果将是：

[ 
  [CCC],
  [CCC, AAA],
  [CCC, AAA, DDD],
  [CCC, AAA, KKK],
  [CCC, AAA, KKK, EEE],
  [ZZZ],
  [ZZZ, BBB],
]

简而言之，我想遍历每个列表中的每个第一个元素并按字母顺序对其进行排序，然后是每个第二个元素并对其进行排序，然后是第三个，然后是第四个，依此类推。有办法吗？

编辑：为避免混淆，这是我的观点：

def page_list(request):


    # Fetch all pages and sort them alphabetically
    queryset = Page.objects.all().order_by("title")
    output = []

    # Generate list of pages and their parents
    for page in queryset:
        output.append(get_list_of_parents(page))

    context = {
        "title": "Page List",
        "page_list": output,
    }

    return render(request, template + '/page_list.html', context)

# Get an array of all parent instances of a Page model
def get_list_of_parents(page, list=None):

    current_page = page 
    parent_list = []    

    if list is not None:
        parent_list = list

    parent_list.append(current_page)

    if current_page.parent is not None:
        parent_list = get_list_of_parents(current_page.parent, parent_list)
    else:
        # if this is the last parent page, reverse the order of list to display list in form of parent path to child
        parent_list.reverse()

    return parent_list

Answer 1

使用页面树：

我定义了这个简单的树结构：

class Page(object):
    def __init__(self, name, children=None):
        self.name = name
        self.children = children or []

    def display(self, indent=""):
        child_repr = [child.display(indent=indent + "  ") for child in self.children]
        return indent + self.name + "\n" + "".join(child_repr)

    def __str__(self):
        return self.display()

display和__str__方法用于打印。

我可以将您的树构建为页面列表：

tree = [
    Page("CCC", [
        Page("AAA", [
            Page("DDD"),
            Page("KKK", [
                Page("EEE")])])]),
    Page("ZZZ", [
        Page("BBB")])]

我可以这样显示结构：

for item in tree:
    print(item)

我得到：

CCC
  AAA
    DDD
    KKK
      EEE

ZZZ
  BBB

为了遍历树，我定义了如下方法：

    def traverse(self, result, stack=None):
        stack = stack or []
        stack.append(self.name)
        result.append(list(stack))
        for child in self.children:
            child.traverse(result, stack)
        stack.pop()

其中 result 是要填写的列表。

用法：

result = []
for item in tree:
    item.traverse(result)

import pprint

pprint.pprint(result)

我会得到：

[['CCC'],
 ['CCC', 'AAA'],
 ['CCC', 'AAA', 'DDD'],
 ['CCC', 'AAA', 'KKK'],
 ['CCC', 'AAA', 'KKK', 'EEE'],
 ['ZZZ'],
 ['ZZZ', 'BBB']]

太棒了！

Answer 2

利用 itertools 中的辅助函数，使用简单高效的单行比较函数进行排序。

>>> import pprint
>>> from itertools import dropwhile, izip_longest
>>> pages = [['CCC', 'AAA'],
...          ['ZZZ', 'BBB'],
...          ['CCC'],
...          ['CCC', 'AAA', 'DDD'],
...          ['CCC', 'AAA', 'DDD', 'EEE'],
...          ['CCC', 'AAA', 'KKK'],
...          ['ZZZ']]
>>> pprint.pprint(sorted(pages, cmp=lambda a, b: cmp(*next(dropwhile(lambda x: not cmp(x[0], x[1]), izip_longest(a, b))))))
[['CCC'],
 ['CCC', 'AAA'],
 ['CCC', 'AAA', 'DDD'],
 ['CCC', 'AAA', 'DDD', 'EEE'],
 ['CCC', 'AAA', 'KKK'],
 ['ZZZ'],
 ['ZZZ', 'BBB']]
>>>

这不仅适用于字符串，也适用于 Page 实例，只要它们具有可比性，即您已在 Page class.

中定义了 __cmp__ 方法

如何根据嵌套列表中的每个元素对嵌套列表进行排序

How can I sort a nested list accordign to each element in nested lists

python

sorting

django

nested-lists