multi nested dictionary from tuples in python

Question

I have this list of tuples

list_of_tuples = [('0', '1'), ('1', '1.1'), ('1', '1.2'), ('1', '1.3'), ('1', '1.4'), ('0', '3'), ('3', '3.1'), ('3', '3.2'), ('3', '3.3'), ('3', '3.4'), ('3', '3.5'), ('0', '4'), ('4', '4.1'), ('4', '4.2'), ('4', '4.3'), ('4', '4.4'), ('4', '4.5'), ('4', '4.6'), ('4', '4.7'), ('4', '4.8'), ('4', '4.9'), ('0', '5'), ('5', '5.1'), ('5', '5.2'), ('5', '5.3'), ('5', '5.4'), ('0', '6'), ('6', '6.1'), ('6', '6.2'), ('6', '6.3'), ('6', '6.4'), ('6', '6.5'), ('0', '7'), ('7', '7.1'), ('7', '7.2'), ('7', '7.3'), ('7.3', '7.3.1'), ('7.3', '7.3.2'), ('7.3', '7.3.3'), ('0', '8'), ('8', '8.1.1'), ('8', '8.1.2'), ('8', '8.2'), ('0', '9'), ('9', '9.1'), ('9', '9.2'), ('0', '10'), ('10', '10.1'), ('10', '10.2'), ('10', '10.3'), ('10.3', '10.3.2'), ('10.3', '10.3.3'), ('10.3', '10.3.4'), ('10.3', '10.3.5'), ('10.3', '10.3.6')

The first value in the tuple is the parent and the second is the value.

(parent,child)

i want the output to be like this.

{ '0': {'1': {'1.1':None, '1.2':None...... } {'3': {'3.1':None/[].. } } }

i can add it to the dictionary but i want it to be nested like a tree with multiple children.

d = defaultdict(list) for k, v in h: d[k].append(v)

Any help is appreciated.

Is your list of edges guaranteed to be in depth-first order? — user2390182
– user2390182, Commented Jan 4, 2017 at 20:39

user2390182 · Accepted Answer · 2017-01-04 21:22:55Z

Patrick's solution is generic and object-oriented. However, it is O(N^2) (N being the number of edges) because it traverses the entire tree for each edge. Since you know that you get the edges in depth-first order, you can save a lot (for large trees: a lot lot!) of time by memorizing your current position in the tree, inserting right where you are, and going back up the tree if needed.

The following is more concise and O(N) without the additional overhead of your own classes and extra-conversion:

from pprint import pprint d = {} crnt = d # memo the crnt subtree stck = [] # stack of (sub)trees along current path for k, v in list_of_tuples: while stck and k not in crnt: crnt = stck.pop() if k not in crnt: crnt[k] = {} stck.append(crnt) crnt = crnt[k] crnt[v] = {} pprint(d) {'0': {'1': {'1.1': {}, '1.2': {}, '1.3': {}, '1.4': {}}, '10': {'10.1': {}, '10.2': {}, '10.3': {'10.3.2': {}, '10.3.3': {}, '10.3.4': {}, '10.3.5': {}, '10.3.6': {}}}, '3': {'3.1': {}, '3.2': {}, '3.3': {}, '3.4': {}, '3.5': {}}, '4': {'4.1': {}, '4.2': {}, '4.3': {}, '4.4': {}, '4.5': {}, '4.6': {}, '4.7': {}, '4.8': {}, '4.9': {}}, '5': {'5.1': {}, '5.2': {}, '5.3': {}, '5.4': {}}, '6': {'6.1': {}, '6.2': {}, '6.3': {}, '6.4': {}, '6.5': {}}, '7': {'7.1': {}, '7.2': {}, '7.3': {'7.3.1': {}, '7.3.2': {}, '7.3.3': {}}}, '8': {'8.1.1': {}, '8.1.2': {}, '8.2': {}}, '9': {'9.1': {}, '9.2': {}}}}

Patrick Haugh · Accepted Answer · 2017-01-05 13:49:48Z

I'm going to whip up a quick tree class that can take this input and build a tree with it, then I'm going to write a method for that class that converts them back to dictionaries

class Tree: def __init__(self, name, parent=None): #parent is None to detect root self.name = name self.parent = parent self.children = [] def add(self, target , child): ''' Does DFS until it finds Tree with name target. Creates a Tree(child) as child of Tree name ''' if self.name == target: self.children.append(Tree(child, self)) return True else: for subtree in self.children: if subtree.add(target, child): return True if self.parent: return False raise ValueError('Bad Parent no such node {}'.format(target)) def dictify(self): d = {} for child in self.children: d.update(child.dictify()) return {self.name: d} list_of_tuples = [('0', '1'), ('1', '1.1'), ('1', '1.2'), ('1', '1.3'), ('1', '1.4'), ('0', '3'), ('3', '3.1'), ('3', '3.2'), ('3', '3.3'), ('3', '3.4'), ('3', '3.5'), ('0', '4'), ('4', '4.1'), ('4', '4.2'), ('4', '4.3'), ('4', '4.4'), ('4', '4.5'), ('4', '4.6'), ('4', '4.7'), ('4', '4.8'), ('4', '4.9'), ('0', '5'), ('5', '5.1'), ('5', '5.2'), ('5', '5.3'), ('5', '5.4'), ('0', '6'), ('6', '6.1'), ('6', '6.2'), ('6', '6.3'), ('6', '6.4'), ('6', '6.5'), ('0', '7'), ('7', '7.1'), ('7', '7.2'), ('7', '7.3'), ('7.3', '7.3.1'), ('7.3', '7.3.2'), ('7.3', '7.3.3'), ('0', '8'), ('8', '8.1.1'), ('8', '8.1.2'), ('8', '8.2'), ('0', '9'), ('9', '9.1'), ('9', '9.2'), ('0', '10'), ('10', '10.1'), ('10', '10.2'), ('10', '10.3'), ('10.3', '10.3.2'), ('10.3', '10.3.3'), ('10.3', '10.3.4'), ('10.3', '10.3.5'), ('10.3', '10.3.6')] root = Tree('0') for parent, child in list_of_tuples: root.add(parent, child) print(root.dictify())

Here is is with pprint (pretty printing)

{'0': {'1': {'1.1': {}, '1.2': {}, '1.3': {}, '1.4': {}}, '10': {'10.1': {}, '10.2': {}, '10.3': {'10.3.2': {}, '10.3.3': {}, '10.3.4': {}, '10.3.5': {}, '10.3.6': {}}}, '3': {'3.1': {}, '3.2': {}, '3.3': {}, '3.4': {}, '3.5': {}}, '4': {'4.1': {}, '4.2': {}, '4.3': {}, '4.4': {}, '4.5': {}, '4.6': {}, '4.7': {}, '4.8': {}, '4.9': {}}, '5': {'5.1': {}, '5.2': {}, '5.3': {}, '5.4': {}}, '6': {'6.1': {}, '6.2': {}, '6.3': {}, '6.4': {}, '6.5': {}}, '7': {'7.1': {}, '7.2': {}, '7.3': {'7.3.1': {}, '7.3.2': {}, '7.3.3': {}}}, '8': {'8.1.1': {}, '8.1.2': {}, '8.2': {}}, '9': {'9.1': {}, '9.2': {}}}}

If you want those empty dicts to be None just change dictify to return {self.name: d if d else None}

Edit: schwobaseggl makes a good point about insertion complexity. Here is a version of the Tree class that takes advantage of ordered inputs

class Tree: def __init__(self, name, parent=None): #parent is None to detect root self.name = name self.parent = parent self.children = [] def add(self, target , child): ''' Accepts additions in DFS order. Relies on the fact that every node will be the direct descendant of the previous node or one of its ancestors. ''' if self.name == target: kiddo = Tree(child, self) self.children.append(kiddo) return kiddo elif self.parent: return self.parent.add(target, child) else: raise ValueError('Bad Parent no such node {}'.format(target)) def dictify(self): d = {} for child in self.children: d.update(child.dictify()) return {self.name: d} list_of_tuples = [('0', '1'), ('1', '1.1'), ('1', '1.2'), ('1', '1.3'), ('1', '1.4'), ('0', '3'), ('3', '3.1'), ('3', '3.2'), ('3', '3.3'), ('3', '3.4'), ('3', '3.5'), ('0', '4'), ('4', '4.1'), ('4', '4.2'), ('4', '4.3'), ('4', '4.4'), ('4', '4.5'), ('4', '4.6'), ('4', '4.7'), ('4', '4.8'), ('4', '4.9'), ('0', '5'), ('5', '5.1'), ('5', '5.2'), ('5', '5.3'), ('5', '5.4'), ('0', '6'), ('6', '6.1'), ('6', '6.2'), ('6', '6.3'), ('6', '6.4'), ('6', '6.5'), ('0', '7'), ('7', '7.1'), ('7', '7.2'), ('7', '7.3'), ('7.3', '7.3.1'), ('7.3', '7.3.2'), ('7.3', '7.3.3'), ('0', '8'), ('8', '8.1.1'), ('8', '8.1.2'), ('8', '8.2'), ('0', '9'), ('9', '9.1'), ('9', '9.2'), ('0', '10'), ('10', '10.1'), ('10', '10.2'), ('10', '10.3'), ('10.3', '10.3.2'), ('10.3', '10.3.3'), ('10.3', '10.3.4'), ('10.3', '10.3.5'), ('10.3', '10.3.6')] root = Tree('0') curr = root for parent, child in list_of_tuples: curr = curr.add(parent, child) print(root.dictify())

Collectives™ on Stack Overflow

multi nested dictionary from tuples in python

2 Answers 2

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Linked

Related