Рекурсивные функции сортировки для списка в 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 Ван Дьен действительно хорош, но мне нужно 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 

Вот еще решение, которое работает только в том случае, если вы можете предположить, что родители уже существуют, когда они вам понадобятся. Дела идут плохо, если у вас есть повторяющиеся группы, поэтому вам нужно настроить его для себя.

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'}]