Python list structure modification

Question

What is the best way to convert the following:

myList = [
          ['ItemB','ItemZ'],
          ['ItemB','ItemP'],
          ['ItemB','ItemJ','Item6'],
          ['ItemB','ItemJ','Item5']
         ]

to this in Python:

newList = ['ItemB',['ItemP','ItemZ',['ItemJ',['Item5','Item6']]]]

I was able to get close using a recursive function that sorted by Len but couldn't figure out a good way to sort by Len then alphabetically. Any help would be greatly appreciated!

Please feel free to share your *I was able to get close using a recursive function* — Jon Clements, Jul 19 '13 at 22:05
The two lists look identical, to my eyes. What am I missing? — Alex Reynolds, Jul 19 '13 at 22:07
what are you trying to do with this "list"? This feels like a tree traversal. — inspectorG4dget, Jul 19 '13 at 22:09
@RyanHaining: I made a bad edit, which got rolled back and then I made the edit I intended to make in the first place — inspectorG4dget, Jul 19 '13 at 22:10
Yes original list is being converted for use with a ui tree widget so the lists need to be nested to represent the tree structure. — jnap, Jul 19 '13 at 22:13
@jnap And this UI toolkit forces you to structure your data in a list this way? — 2rs2ts, Jul 19 '13 at 22:14
Ah! This is like a nested menu. You want to take as input a list of paths to menu items, and convert it to a tree representation of the menu. Am I right? — user2357112, Jul 19 '13 at 22:15
@2rs2ts yes. And it needs to be scalable so if one of the original list elements had a Len of n that would be supported. — jnap, Jul 19 '13 at 22:16
Menu would not go more than 3-4 levels deep but if written that right way, that shouldn't matter. (In theory) :) — jnap, Jul 19 '13 at 22:18
@All I'll post my recursive function tonight...in transit right now and don't have access to work network. — jnap, Jul 19 '13 at 22:19
Are you sure your expected result is correct? Shouldn't it be `['ItemB', ['ItemP', 'ItemZ', 'ItemJ', ['Item5', 'Item6']]]`? I see no sense in that bracket after `ItemZ`. — tobias_k, Jul 19 '13 at 22:26
not that it makes sense, cause it doesn't gracefully allow `P` and `Z` to have items added to them. — Ryan Haining, Jul 19 '13 at 22:30
`P` and `Z` shouldn't have items added to them. They're buttons, not submenus. — user2357112, Jul 19 '13 at 22:30
The widget requires the list in the new list format. It was correctly posted. — jnap, Jul 19 '13 at 22:36
The ui tree widget is a python wrapped c# object so there may be a proprietary implementation here. — jnap, Jul 19 '13 at 22:40
Are the elements of `myList` file paths? I'm wondering why your input is in this format. — user2357112, Jul 19 '13 at 23:11

score 2 · Answer 1 · edited Jul 07 '20 at 18:45

Maybe not the most elegant way, but this seems to work:

First, we turn the list of lists into a dictionary using a defaultdict of defaultdicts of defaultdicts, aka infinitedict

myList = [['ItemB','ItemZ'],['ItemB','ItemP'],['ItemB','ItemJ','Item6'],['ItemB','ItemJ','Item5']]

from collections import defaultdict
infinitedict = lambda: defaultdict(infinitedict)
dictionary = infinitedict()
for item in myList:
    d = dictionary
    for i in item:
        d = d[i]

Now, we can use a recursive function to turn that dictionary back into a tree-styled list:

def to_list(d):
    lst = []
    for i in d:
        lst.append(i)
        if d[i]:
            lst.append(to_list(d[i]))
    return lst

The output is a bit different from your expected output, but this seems to make more sense to me:

>>> print(to_list(dictionary))
['ItemB', ['ItemZ', 'ItemJ', ['Item6', 'Item5'], 'ItemP']]

Or, closer to your expected result (but still not exactly the same, as the order is scrambled up because of the intermediate step with the dictionary) using this instead:

def to_list(d):
    return [[i] + [to_list(d[i])] if d[i] else i for i in d]

Output:

>>> print(to_list(dictionary)[0])
['ItemB', ['ItemZ', ['ItemJ', ['Item6', 'Item5']], 'ItemP']]

If you can get it to be `['ItemB', ['ItemZ', ['ItemJ', ['Item6', 'Item5']], 'ItemP']]` that'll be what OP wants. — 2rs2ts, Jul 19 '13 at 22:38

user2357112 · Answer 2 · 2013-07-19T23:08:43.987

Similar to tobias_k's answer, but in the format you wanted, sorted and all. ~~(I think.)~~ Okay, it's tested and seems to be working now.

We turn the path list into a tree with defaultdict, then turn the defaultdict-based tree into a sorted list-based form recursively.

from collections import defaultdict

def tree():
    # A dict-based tree that automatically creates nodes when you access them.
    # Note that this does not store a name for itself; it's closer to a dropdown
    # menu than the little button you click to display the menu, or the contents
    # of a directory rather than the directory itself.
    return defaultdict(tree)

def paths_to_tree(paths):
    # Make a tree representing the menu.
    menu = tree()
    for path in myList:
        add_to = menu

        # Traverse the tree to automatically create new tree nodes.
        for name in path:
            add_to = add_to[name]
    return menu

def sort_key(item):
    if isinstance(item, list):
        return 1, item[0]
    else:
        # It's a string
        return 0, item

# Recursively turn the tree into nested lists.
def tree_to_lists(menu):
    lists = [[item, tree_to_lists(menu[item])] if menu[item] else item
             for item in menu]
    lists.sort(key=sort_key)
    return lists

# Note the [0].
output = tree_to_lists(paths_to_tree(myList))[0]

Python list structure modification

2 Answers2