python - Python中列表的递归排序函数

Question

我想要一个如下所示的列表:

groups = ["foo", "bar", "foo::fone", "foo::ftwo", "foo::ftwo::ffone"]

并将其转换为嵌套列表，可能采用以下格式，但我愿意接受建议:

groups_sorted = [{
                    "name":"foo",
                    "children": [
                                  {
                                    "name": "foo::fone",
                                    "children": [ ... ]
                                  }, ...
                                ]
                 }, ...
                ]

以便使用 :: 上的层次结构拆分对列表进行排序。我需要将每个 children 键自行列出，因为列表的原始顺序很重要。

我已经玩了几个小时，并且能够从单个顶部节点开始创建一个递归字典，但我无法完成最后一点。在下面找到我的工作:

def children_of(node, candidates):
    children = []
    remainder = []
    for c in candidates:
        sub = node + "::"
        if c.startswith(sub):
            try:
                c[len(sub):].index("::") # any more separators = not a child
                remainder.append(c)
            except ValueError: # a child
                children.append(c)    
        else: #not related
            remainder.append(c)
    return children, remainder

def sortit(l):
    if l:
        el = l.pop(0)
        children, remainder = children_of(el,l)
        if children:    
            return { "name": el,
                     "children": [sortit([c]+remainder) for c in children]
                   }
        else:
            return { "name": el }

编辑:@Thijs van Dien 的解决方案非常好，但我需要 2.6 兼容性，这阻止了我使用 OrderDicts。

Answer 1

像这样的东西怎么样？

from collections import OrderedDict

dic = OrderedDict()

def insert(name):
    current_dic = dic
    current_name = ''
    for name_elem in name.split('::'):
        current_name += ('::' if current_name else '') + name_elem
        if not current_name in current_dic:
            current_dic[current_name] = OrderedDict()
        current_dic = current_dic[current_name]

for group in ["foo", "bar", "foo::fone", "foo::ftwo", "foo::ftwo::ffone"]:
    insert(group)

这将为您提供以下结构:

{'bar': {}, 'foo': {'foo::fone': {}, 'foo::ftwo': {'foo::ftwo::ffone': {}}}}

OrderedDict 确保保留顺序，因此您不需要使用任何list。另外，您不需要使用递归，因为 Python 中不推荐使用递归。

如果您在标准库中没有 OrderedDict，因为您使用的是 Python 2.6，则可以安装它:

pip install ordereddict

然后更改导入:

from ordereddict import OrderedDict

这是另一种解决方案，仅当您可以假设 parent 在您需要时已经存在时才有效。如果您有重复的组，事情就会变得很糟糕，因此您需要自己进行调整。

children_of_name = dict([('', list())]) # Access root with empty string

def insert(name):
    parent_name = '::'.join(name.split('::')[:-1])
    dic = dict([('name', name), ('children', list())])
    children_of_name[parent_name].append(dic)
    children_of_name[name] = dic['children']

for group in ["foo", "bar", "foo::fone", "foo::ftwo", "foo::ftwo::ffone"]:
    insert(group)

它为您提供了您建议的结构:

[{'children': [{'children': [], 'name': 'foo::fone'},
               {'children': [{'children': [], 'name': 'foo::ftwo::ffone'}],
                'name': 'foo::ftwo'}],
  'name': 'foo'},
 {'children': [], 'name': 'bar'}]