Create a hierarchy from a dictionary of lists

Question

I have a dictionary of lists:

a = {
        'a': [1, 2, 3],
        'b': [1, 2, 4],
        'c': [1, 2],
        'd': [1, 2, 3, 4, 5],
        'e': [3],
        'f': [3, 7],
        'g': [3, 3],
        'h': [3, 3, 3, 3, 3],
        'i': [3, 3, 3, 3, 4],
    }

And I would like to create hierarchical structure from this dictionary which will group items in the similar manner (exact structure does not matter, as well as the relation between elements is preserved):

              /  \
             /    \
            e      c
           /\      /\
          f  g    a  b
             /\   |
            h  i  d

The hierarchy goes as follows: array g is a prefix of array h and i and therefore it is their ancestor. But e is a prefix of g, so it e is an ancestor of g.

Here is my idea how to achieve this result.

• Sort the dictionary based on the number of elements in the list, which I was able to achieve with s = sorted(a.items(), key=lambda e: len(e[1])). This will give me the following structure:

.

('e', [3])
('c', [1, 2])
('g', [3, 3])
('f', [3, 7])
('a', [1, 2, 3])
('b', [1, 2, 4])
('d', [1, 2, 3, 4, 5])
('h', [3, 3, 3, 3, 3])

• Right now I can find first parents by iterating through elements and checking if an element is a prefix of other elements. Starting with the first one. e is a prefix of g, f, and h. And c is a prefix of a, b, d. So these two elements are the parents.

• right now I understand that I have to use recursion to enter inside of each parent and to perform the same operation, but I was not able to come up with a right solution.

So does anyone knows how to approach this problem. Or am I over-complicating things and there is an easier way to achieve the solution.

P.S. this is not a homework assignment or interview question (also it might be). This is just my abstraction from a problem I am trying to solve.

Answer 1

Other people already give the methord, I just write some code here:

First sort:

t = sorted(a.items(), key=lambda x: x[1])

The build the structure

ret = {}

def build(ret, upv):
    if not t:
        return (None, None)
    k, v = t.pop(0)
    while k and v:
        if upv and v[:len(upv)] != upv:
            return (k, v)
        r = {}
        ret[k] = r
        k, v = build(r, v)
    return None, None

build(ret, None)
print ret