Fun transformation problem

[Dale Strickland-Clark]

A guy in the office has come up with this interesting transformation
problem. We have a solution but I'm sure there's a neater, more 'pythonic'
approach.

I thought this might appeal to some here:

I want a function to convert a list of tuples into a hierarchy of
dictionaries.  Let me first demonstrate with an example:

lstA = [(1, 2, 3), (1, 3, 4), (2, 5, 6)]
dctA = fncA(lstA)
print dctA {1: {2: 3, 3: 4}, 2: {5: 6}}

I essentially want the definition to fncA.  Here is another example:

lstA = [(1, 2, 3, 4) ,(3, 4, 5, 6), (3, 4, 6, 7), (3, 4, 6, 8), (3, 4, 5, 1), (3, 4, 7, 9)]
dctA = fncA(lstA)
print dctA {1: {2: {3: 4}}, 3: {4: {5: 1, 6: 8, 7: 9}}}

Each tuple in the original list must be unique after the last value is
excluded (since these values are used to form the "hierarchical key".

I have written a function, which seems to work but looks very cumbersome.
Could anyone point me to a simpler solution?



Dale Strickland-Clark
Riverhall Systems

 

[anton muhin]

A guy in the office has come up with this interesting transformation
problem. We have a solution but I'm sure there's a neater, more 'pythonic'
approach.

I thought this might appeal to some here:

I want a function to convert a list of tuples into a hierarchy of
dictionaries. Let me first demonstrate with an example:

lstA = [(1, 2, 3), (1, 3, 4), (2, 5, 6)]
dctA = fncA(lstA)
print dctA

{1: {2: 3, 3: 4}, 2: {5: 6}}


I essentially want the definition to fncA. Here is another example:

lstA = [(1, 2, 3, 4) ,(3, 4, 5, 6), (3, 4, 6, 7), (3, 4, 6, 8), (3, 4,

5, 1), (3, 4, 7, 9)]

{1: {2: {3: 4}}, 3: {4: {5: 1, 6: 8, 7: 9}}}


Each tuple in the original list must be unique after the last value is
excluded (since these values are used to form the "hierarchical key".

I have written a function, which seems to work but looks very cumbersome.
Could anyone point me to a simpler solution?



Dale Strickland-Clark
Riverhall Systems

The following:

def transform(l):
d = {}

for t in l:
c = d
for e in t[:-2]:
c = c.setdefault(e, {})
c[t[-2]] = t[-1]

return d

seems clear enough for me.

with the best regards,
anton.

 

[Tim Leslie]

This is what I came up with. It's recursive, so it could get you into
trouble with longer lists, but hey, it's late at night and it'll do
for now

def g(d, lst):
head = lst[0]
tail = lst[1:]
if not tail:
return head
else:
d[head] = g(d.get(head, {}), tail)
return d

def f(lst):
d = {}
for xs in lst:
d = g(d, xs)
return d

Cheers,

Tim

A guy in the office has come up with this interesting transformation
problem. We have a solution but I'm sure there's a neater, more 'pythonic'
approach.

I thought this might appeal to some here:

I want a function to convert a list of tuples into a hierarchy of
dictionaries. Let me first demonstrate with an example:

lstA = [(1, 2, 3), (1, 3, 4), (2, 5, 6)]
dctA = fncA(lstA)
print dctA

{1: {2: 3, 3: 4}, 2: {5: 6}}


I essentially want the definition to fncA. Here is another example:

lstA = [(1, 2, 3, 4) ,(3, 4, 5, 6), (3, 4, 6, 7), (3, 4, 6, 8), (3, 4,

5, 1), (3, 4, 7, 9)]

dctA = fncA(lstA)
print dctA

{1: {2: {3: 4}}, 3: {4: {5: 1, 6: 8, 7: 9}}}


Each tuple in the original list must be unique after the last value is
excluded (since these values are used to form the "hierarchical key".

I have written a function, which seems to work but looks very cumbersome.
Could anyone point me to a simpler solution?



Dale Strickland-Clark
Riverhall Systems

The following:

def transform(l):
d = {}

for t in l:
c = d
for e in t[:-2]:
c = c.setdefault(e, {})
c[t[-2]] = t[-1]

return d

seems clear enough for me.

with the best regards,
anton.

 

[Dale Strickland-Clak]

Thanks to everyone for your replies. Very interesting.

It is not too embarrasing to admit that these were better than we'd come
up with.

My colleague will be getting to grips with a newsreader in the near future
and may be along later to express his own gratitude.

 

[John Lenton]

Thanks to everyone for your replies. Very interesting.

It is not too embarrasing to admit that these were better than we'd come
up with.

My colleague will be getting to grips with a newsreader in the near future
and may be along later to express his own gratitude.

FYI, that goofy dictionary thing you're building is called a 'trie'.


--
John Lenton ([email protected]) -- Random fortune:
No one can guarantee the actions of another.
-- Spock, "Day of the Dove", stardate unknown

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)

iD8DBQFBL6rkgPqu395ykGsRAnr1AJ4+U/wTqh8XHZYZaDpYphIVBDqpAACeLLvP
/mkmNreb9+mo3WVTFsCDbNM=
=SKUd
-----END PGP SIGNATURE-----

 

[Martin Maney]

FYI, that goofy dictionary thing you're building is called a 'trie'.

And in some applications it may be handy to be able to construct the
trie piece by piece, or to add entries to it. (BTW, am I wrong in
thinking that tries in general aren't restricted to having all leaf
nodes at the same level as the examples in this all do? Not that I'm
complaining, since I'm not going to handle that general case either!)
So I'll start with a function to add a single leaf to a trie:

def add2trie(car, cdr, trie):
if len(cdr) == 1:
trie[car] = cdr[0]
else:
if not trie.has_key(car):
trie[car] = {}
add2trie(cdr[0], cdr[1:], trie[car])

....and then the requested function is trivial:

def f(lstlst):
trie = {}
for lst in lstlst:
add2trie(lst[0], lst[1:], trie)
return trie

car and cdr are intrusions from you-can-guess-where that suggested
themselves in the first hack which had 'way too many occurences of lst[0]
in it.

<digression>

BTW, the first sketch (which I decided I didn't like for its
unnecessary rebinding of existing subtries) could have made good use of
conditional assignment (sorry, it just keeps coming up as I skim
through the backlog today). It would have gone something like...

def add2trie(lst, trie):
trie[lst[0]] = (if len(lst) == 2: lst[1]
else: add2trie(lst[1:], trie.get(lst[0], {}))
return trie

Obviously this is untested code, and to be honest I don't much like
this form when it has to spread across lines like that. OTOH, it's an
amusing example, since it uses within the general conditional
expression one of Python's existing special-case hacks that wouldn't be
necessary (though it might still be handy) if Python had conditional
expressions.

</digression>