Recursive sorting function for list in Python

Question

I want to take a list like the following:

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

And convert it into a nested list, probably in the following format, but I'm open to suggestions:

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

So that the list is sorted using a hierarchy split on ::. I need each of the children keys to be lists themselves as the original order of the list is important.

I've played around for a few hours and been able to create a recursive dictionary starting from a single top node, but I couldn't do the last bit. Find my workings below:

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 }

Edit: @Thijs van Dien's solution is really good but I need 2.6 compatibility which prevents me some using OrderDicts.

Thijs van Dien · Accepted Answer · 2013-09-15 00:38:34Z

3

How about something like this instead?

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)

That gives you the following structure:

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

OrderedDict makes sure that order is preserved, so you don't need to use any list. Also, you don't need to use recursion, as it is not recommended in Python.

If you don't have OrderedDict in the standard library, because you're using Python 2.6, you can install it:

pip install ordereddict

Then change the import:

from ordereddict import OrderedDict

Here's another solution that works only if you can assume that parents already exist when you need them. Things go bad if you have duplicate groups, so you need to adjust it for that yourself.

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)

It gives you the structure that you proposed:

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

edited Sep 15, 2013 at 0:38

answered Sep 14, 2013 at 21:30

Thijs van Dien

6,6442 gold badges32 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Ian Clark Over a year ago

Thanks - sorry this is a fantastic answer but I can't use OrderedDicts as we're using Python 2.6

Thijs van Dien Over a year ago

@IanClark Please, please list such requirements in the OP... However, you can still look up an OrderedDict recipe; you don't need to take it from the standard library.

Thijs van Dien Over a year ago

@IanClark Added instructions to get OrderedDict.

Ian Clark Over a year ago

Thanks - unfortunately I don't have access to the server, so I'll need to stick to the standard 2.6 library

Thijs van Dien Over a year ago

@IanClark Your last option is to manually paste in this recipe: code.activestate.com/recipes/576693-ordered-dictionary-for-py24. I see no point in reinventing it. And squared time complexity, what are you talking about? The code above is linear with respect to the number of elements. You might only have issues with very deep nesting because it always walks down from the top (with constant time lookups, though). You could make it smarter to avoid that. Think of some kind of binary search for which parent already exists.

|

Collectives™ on Stack Overflow

Recursive sorting function for list in Python

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related