CODEWITHSUNDEEP
pythonlist
jnap
jnap

Reputation: 23

Python list structure modification

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!

Upvotes: 2

Views: 171

Answers (2)

tobias_k
tobias_k

Reputation: 82929

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

Upvotes: 2

user2357112
user2357112

Reputation: 281594

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]

Upvotes: 1

Related Questions