Create a nested tree from list

Question

From a list of lists, I would like to create a nested dictionary of which the keys would point to the next value in the sublist. In addition, I would like to count the number of times a sequence of sublist values occurred.

Example:

From a list of lists as such:

[['a', 'b', 'c'],
['a', 'c'],
['b']]

I would like to create a nested dictionary as such:

{
  'a': {
          {'b': 
                {
                'c':{}
                'count_a_b_c': 1
                }
            'count_a_b*': 1
          }, 
          {'c': {},
           'count_a_c': 1
          }
          'count_a*': 2
        },
  {
  'b':{},
  'count_b':1
  }
}

Please note that the names of the keys for counts do not matter, they were named as such for illustration.

Have you made any attempts to accomplish this that you are able to share? — rs311, Nov 17 '18 at 10:54
Unfortunately, none of my attempts were fruitful. I did spend several hours on the problem. The main problem is how to automate the nested structure with a for loop... — micoco, Nov 17 '18 at 11:01

hiro protagonist · Accepted Answer · 2018-11-17T12:06:02.653

i was curious how i would do this and came up with this:

lst = [['a', 'b', 'c'],
['a', 'c'],
['b']]

tree = {}
for branch in lst:
    count_str = 'count_*'
    last_node = branch[-1]
    cur_tree = tree
    for node in branch:
        if node == last_node:
            count_str = count_str[:-2] + f'_{node}'
        else:
            count_str = count_str[:-2] + f'_{node}_*'
        cur_tree[count_str] = cur_tree.get(count_str, 0) + 1
        cur_tree = cur_tree.setdefault(node, {})

nothing special happening here...

for your example:

import json
print(json.dumps(tree, sort_keys=True, indent=4))

produces:

{
    "a": {
        "b": {
            "c": {},
            "count_a_b_c": 1
        },
        "c": {},
        "count_a_b_*": 1,
        "count_a_c": 1
    },
    "b": {},
    "count_a_*": 2,
    "count_b": 1
}

it does not exactly reproduce what you imagine - but that is in part due to the fact that your desired result is not a valid python dictionary...

but it may be a starting point for you to solve your problem.

could you pls take a look this [question](https://stackoverflow.com/questions/56636774/constructing-a-tree-view-from-a-nested-list-using-anytree-treelib) — steven, Jun 17 '19 at 19:06

Create a nested tree from list

1 Answers1