Group items by their ancestors

Assume we have an array:

l = ["1", "1.1", "1.1.1", "2", "3"]

What is the efficent way to build such dict structure:

d = {"1": [{"1.1": [{"1.1.1": []}]}], "2": [], "3": []}

I suggest doing it in three steps.

• Transform l into [['1'], ['1', '1'], ['1', '1', '1'], ['2'], ['3']] using str.split().
• Write a function make_groups that groups by first element.
• Write a recursive function make_tree that applies make_groups once, then applies make_tree recursively to each group.

If this is for learning purposes, I encourage you to try following the three points above, without looking at the code below.

l0 = ["1", "1.1", "1.1.1", "2", "3"]
l = 
展开收缩
 # [['1'], ['1', '1'], ['1', '1', '1'], ['2'], ['3']]

def make_groups(l, depth=0):
    d = {}
    for x in l:
        if len(x) > depth:
            d.setdefault('.'.join(x[:depth+1]), []).append(x)
    return d
# print(make_groups(l))
# {'1': [['1'], ['1', '1'], ['1', '1', '1']], '2': [['2']], '3': [['3']]}

def make_tree(l, depth=0):
    d = make_groups(l, depth)
    for k, v in d.items():
        d[k] = make_tree(v, depth+1)
    return d
# print(make_tree(l))
# {'1': {'1.1': {'1.1.1': {}}}, '2': {}, '3': {}}

This is actually pretty simple. Note it requires well formed list that is you can't jump to 1.1.1 from 1 for example.

First build a dictionary for each value as key and empty list as value. And then go through each key and if it has a "." then go to the key which is to left of the "." and append this dictionary to the list for that parent key.
And finally remove all the keys which have a "."

d = {e:[] for e in l}
for k, v in d.items():
    if "." in k:
        p = k[:k.rindex(".")]
        d
.append({k:v})
d = {k: v for k, v in d.items() if "." not in k}
print(d)

{'1': [{'1.1': [{'1.1.1': []}]}], '2': [], '3': []}

For a more basic/fundamental approach without any recursion,

1. we can Sort our list based on the elements structure
2. Reformat the list elements by finding the "Head" element and create a tail structure.
3. Finally we append them to our dictionary

Here is my main code

l=['1', '1.1', '1.1.1', '1.1.2', '1.1.3','1.1.2.1','2', '2.1', '2.2', '3']
t=l.copy()
from functions import maxd,d,head,apnd,disp
for j in range(0,len(t)):
i=0
while i<len(t):
#if j==4 and i==0:print(t)
if d(t[i])==maxd(t):
h=head(t,t[i])
if type(t[i])==str:t[i]={t[i]:[]}
apnd(t,h,i)
i=i+1
print(t)
disp(t)

and here is the functions definition

def d(x):
if type(x)==str:return len(x.split('.'))
else:
x=list(x.keys())[0]
return d(x)
def comp(a,b):
A=a.split('.')
B=b.split('.')
n=min(len(A),len(B))
for i in range(0,n):
if int(A[i])>int(B[i]):
return True
elif int(A[i])<int(B[i]):
return False
else:
if len(A)>len(B):
return True
else:
return False
def swap(l,a,b):
temp=l[a]
l[a]=l[b]
l[b]=temp
def sort(l):
for j in range(0,len(l)-1):
for i in range(0,len(l)-1):
if comp(l[i],l[i+1])==True:
swap(l,i,i+1)
return l
def lstfmt(l):
i=0
while i<(len(l)-1):
if d(l[i])==d(l[i+1]):
k=i+1
while(d(l[i])==d(l[k])):
k=k+1
l[i]=l[i:k]
del l[i+1:k]
i=i+1
return l
def maxd(l):
maxd=0
for i in l:
if d(i)>maxd:
maxd=d(i)
return maxd
import re
def head(t,x):
if type(x)==str:
for i in range(0,len(t)):
if x!=t[i]:
if d(x)==d(t[i])+1:
if type(t[i])==str:
if re.search('^'+t[i],x):
return i
else:
if re.search('^'+list(t[i].keys())[0],x):
return i
else:
try:return t.index(x)
except ValueError:return -1
else:
x=list(x.keys())[0]
return head(t,x)
def apnd(t,a,b):
if a!=-1:
if a!=b:
if type(t[a])==str:
t[a]={t[a]:[t[b]]}
else:
t[a][list(t[a].keys())[0]].append(t[b])
del t[b]
if a==-1:
if type(t[b])==str:t[b]={t[b]:[]}
def disp(l):
for i in l:
for j in i:
print(j)
print(i[j])