Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > permuting over nested dicts?

Reply
Thread Tools

permuting over nested dicts?

 
 
Christian Meesters
Guest
Posts: n/a
 
      10-31-2007
Hoi,

I have the following data structure (of variable size actually, to make
things simple, just that one):
d = {'a': {'x':[1,2,3], 'y':[4,5,6]},
'b': {'x':[7,8,9], 'y':[10,11,12]}}
This can be read as a dict of possibilities: The entities 'a' and 'b' have
the parameters 'x' and 'y', each. And d['a']['x'] can be either 1 or 2 or
3. Does anybody know a convenient (and fast) way to permute over all
possible nested dicts like
{'a': {'x':1, 'y':4},
'b': {'x':7, 'y':10}}
and
{'a': {'x':2, 'y':4},
'b': {'x':7, 'y':10}}
and so forth?

Any link or snippet is appreciated.

TIA
Christian
 
Reply With Quote
 
 
 
 
Paddy
Guest
Posts: n/a
 
      10-31-2007
On Oct 31, 5:21 pm, Christian Meesters <(E-Mail Removed)> wrote:
> Hoi,
>
> I have the following data structure (of variable size actually, to make
> things simple, just that one):
> d = {'a': {'x':[1,2,3], 'y':[4,5,6]},
> 'b': {'x':[7,8,9], 'y':[10,11,12]}}
> This can be read as a dict of possibilities: The entities 'a' and 'b' have
> the parameters 'x' and 'y', each. And d['a']['x'] can be either 1 or 2 or
> 3. Does anybody know a convenient (and fast) way to permute over all
> possible nested dicts like
> {'a': {'x':1, 'y':4},
> 'b': {'x':7, 'y':10}}
> and
> {'a': {'x':2, 'y':4},
> 'b': {'x':7, 'y':10}}
> and so forth?
>
> Any link or snippet is appreciated.
>
> TIA
> Christian


from http://aspn.activestate.com/ASPN/Coo.../Recipe/502199
import comb2
# (I wish)!

for xa,ya,xb,yb in comb2([1,2,3], [4,5,6], [7,8,9], [10,11,12]):
print {'a': {'x': xa, 'y': ya},
'b': {'x': xb, 'y': yb}}

Should work although untested.

- Paddy.

 
Reply With Quote
 
 
 
 
Anand
Guest
Posts: n/a
 
      11-01-2007
On Oct 31, 10:21 pm, Christian Meesters <(E-Mail Removed)> wrote:
> Hoi,
>
> I have the following data structure (of variable size actually, to make
> things simple, just that one):
> d = {'a': {'x':[1,2,3], 'y':[4,5,6]},
> 'b': {'x':[7,8,9], 'y':[10,11,12]}}
> This can be read as a dict of possibilities: The entities 'a' and 'b' have
> the parameters 'x' and 'y', each. And d['a']['x'] can be either 1 or 2 or
> 3. Does anybody know a convenient (and fast) way to permute over all
> possible nested dicts like
> {'a': {'x':1, 'y':4},
> 'b': {'x':7, 'y':10}}
> and
> {'a': {'x':2, 'y':4},
> 'b': {'x':7, 'y':10}}
> and so forth?
>
> Any link or snippet is appreciated.
>


This code works for dictionaries of any nested level.


def combine(key, value, permutations):
"""Adds key-value pair to every dictionary in the permutations.
If value is a list, then every key-element pair is added to every
permutation.
>>> list(combine('a', 1, [{}]))

[{'a': 1}]
>>> list(combine('a', [1, 2], [{}]))

[{'a': 1}, {'a': 2}]
>>> list(combine('a', 1, [{'b': 1}, {'b': 2}]))

[{'a': 1, 'b': 1}, {'a': 1, 'b': 2}]
>>> list(combine('a', [1, 2], [{'b': 1}, {'b': 2}]))

[{'a': 1, 'b': 1}, {'a': 2, 'b': 1}, {'a': 1, 'b': 2}, {'a':
2, 'b': 2}]
"""
for p in permutations:
if isinstance(value, list):
for v in value:
q = p.copy()
q[key] = v
yield q
else:
p[key] = value
yield p


def permute(d):
"""
>>> list(permute({'x': [1, 2, 3]}))

[{'x': 1}, {'x': 2}, {'x': 3}]
>>> list(permute({'a': [1, 2], 'b': [3, 4]}))

[{'a': 1, 'b': 3}, {'a': 2, 'b': 3}, {'a': 1, 'b': 4}, {'a': 2,
'b': 4}]
>>> list(permute({'a': {'x': [1, 2]}, 'b': [3, 4]}))

[{'a': {'x': 1}, 'b': 3}, {'a': {'x': 2}, 'b': 3}, {'a': {'x': 1},
'b': 4}, {'a': {'x': 2}, 'b': 4}]
"""
if not d:
return [{}]
else:
k, v = d.popitem()
if isinstance(v, dict):
v = list(permute(v))
return combine(k, v, permute(d))



 
Reply With Quote
 
Anand
Guest
Posts: n/a
 
      11-01-2007
On Nov 1, 2:12 pm, Anand <(E-Mail Removed)> wrote:
> On Oct 31, 10:21 pm, Christian Meesters <(E-Mail Removed)> wrote:
>
>
>
> > Hoi,

>
> > I have the following data structure (of variable size actually, to make
> > things simple, just that one):
> > d = {'a': {'x':[1,2,3], 'y':[4,5,6]},
> > 'b': {'x':[7,8,9], 'y':[10,11,12]}}
> > This can be read as a dict of possibilities: The entities 'a' and 'b' have
> > the parameters 'x' and 'y', each. And d['a']['x'] can be either 1 or 2 or
> > 3. Does anybody know a convenient (and fast) way to permute over all
> > possible nested dicts like
> > {'a': {'x':1, 'y':4},
> > 'b': {'x':7, 'y':10}}
> > and
> > {'a': {'x':2, 'y':4},
> > 'b': {'x':7, 'y':10}}
> > and so forth?

>
> > Any link or snippet is appreciated.

>
> This code works for dictionaries of any nested level.
>
> def combine(key, value, permutations):
> """Adds key-value pair to every dictionary in the permutations.
> If value is a list, then every key-element pair is added to every
> permutation.
> >>> list(combine('a', 1, [{}]))

> [{'a': 1}]
> >>> list(combine('a', [1, 2], [{}]))

> [{'a': 1}, {'a': 2}]
> >>> list(combine('a', 1, [{'b': 1}, {'b': 2}]))

> [{'a': 1, 'b': 1}, {'a': 1, 'b': 2}]
> >>> list(combine('a', [1, 2], [{'b': 1}, {'b': 2}]))

> [{'a': 1, 'b': 1}, {'a': 2, 'b': 1}, {'a': 1, 'b': 2}, {'a':
> 2, 'b': 2}]
> """
> for p in permutations:
> if isinstance(value, list):
> for v in value:
> q = p.copy()
> q[key] = v
> yield q
> else:
> p[key] = value
> yield p
>
> def permute(d):
> """
> >>> list(permute({'x': [1, 2, 3]}))

> [{'x': 1}, {'x': 2}, {'x': 3}]
> >>> list(permute({'a': [1, 2], 'b': [3, 4]}))

> [{'a': 1, 'b': 3}, {'a': 2, 'b': 3}, {'a': 1, 'b': 4}, {'a': 2,
> 'b': 4}]
> >>> list(permute({'a': {'x': [1, 2]}, 'b': [3, 4]}))

> [{'a': {'x': 1}, 'b': 3}, {'a': {'x': 2}, 'b': 3}, {'a': {'x': 1},
> 'b': 4}, {'a': {'x': 2}, 'b': 4}]
> """
> if not d:
> return [{}]
> else:
> k, v = d.popitem()
> if isinstance(v, dict):
> v = list(permute(v))
> return combine(k, v, permute(d))


better solution:

def permute(d):
def newdict(d, k, v):
d = d.copy()
d[k] = v
return d

permutations = [{}]
for key, value in d.items():
if isinstance(value, dict):
value = list(permute(value))
elif not isinstance(value, list):
value = [value]
permutations = [newdict(p, key, v) for p in permutations for v
in value]
return permutations

 
Reply With Quote
 
Ant
Guest
Posts: n/a
 
      11-01-2007
On Nov 1, 9:12 am, Anand <(E-Mail Removed)> wrote:
....
> This code works for dictionaries of any nested level.


At least up to the max recursion depth.

--
Ant.

 
Reply With Quote
 
Christian Meesters
Guest
Posts: n/a
 
      11-01-2007
Thanks everyone,

I knew there must be a snippet somewhere, just couldn't find one! (Just for
the sake of completeness: Order doesn't matter and I hope that with my data
I won't reach the recursion depth limit.)

Christian
 
Reply With Quote
 
Boris Borcic
Guest
Posts: n/a
 
      11-01-2007
Christian Meesters wrote:
> Hoi,
>
> I have the following data structure (of variable size actually, to make
> things simple, just that one):
> d = {'a': {'x':[1,2,3], 'y':[4,5,6]},
> 'b': {'x':[7,8,9], 'y':[10,11,12]}}
> This can be read as a dict of possibilities: The entities 'a' and 'b' have
> the parameters 'x' and 'y', each. And d['a']['x'] can be either 1 or 2 or
> 3. Does anybody know a convenient (and fast) way to permute over all
> possible nested dicts like
> {'a': {'x':1, 'y':4},
> 'b': {'x':7, 'y':10}}
> and
> {'a': {'x':2, 'y':4},
> 'b': {'x':7, 'y':10}}
> and so forth?
>
> Any link or snippet is appreciated.
>
> TIA
> Christian


def cases(d) :
import re
bits = re.split('(\[.*?\])',repr(d))
vv = [('_%s' % k, ' for _%s in %s' % (k,v))
for k,v in enumerate(bits[1::2])]
expr = [p+v for p,(v,_) in zip(bits[::2],vv)]+bits[-1:]+[v for _,v in vv]
return eval('(%s)' % ''.join(expr))

for t in cases({'a': {'x':[1,2,3], 'y':[4,5,6]},
'b': {'x':[7,8,9], 'y':[10,11,12]}}) :
print t


{'a': {'y': 4, 'x': 1}, 'b': {'y': 10, 'x': 7}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 10, 'x': 8}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 10, 'x': 9}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 11, 'x': 7}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 11, 'x': 8}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 11, 'x': 9}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 12, 'x': 7}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 12, 'x': 8}}
{'a': {'y': 4, 'x': 1}, 'b': {'y': 12, 'x': 9}}
{'a': {'y': 4, 'x': 2}, 'b': {'y': 10, 'x': 7}}
<snip/>

Caveats : (1) assert eval(repr(d))==d
(2) no square bracket in either keys or values
 
Reply With Quote
 
Paddy
Guest
Posts: n/a
 
      11-06-2007
On Nov 1, 10:51 am, Christian Meesters <(E-Mail Removed)> wrote:
> Thanks everyone,
>
> I knew there must be a snippet somewhere, just couldn't find one! (Just for
> the sake of completeness: Order doesn't matter and I hope that with my data
> I won't reach the recursion depth limit.)
>
> Christian


My solution using comb2 is recursive so there is no problem with
recursion depth.

- Paddy.

 
Reply With Quote
 
Boris Borcic
Guest
Posts: n/a
 
      11-08-2007
Boris Borcic wrote:
> Christian Meesters wrote:
>> Hoi,
>>
>> I have the following data structure (of variable size actually, to make
>> things simple, just that one):
>> d = {'a': {'x':[1,2,3], 'y':[4,5,6]},
>> 'b': {'x':[7,8,9], 'y':[10,11,12]}}
>> This can be read as a dict of possibilities: The entities 'a' and 'b'
>> have
>> the parameters 'x' and 'y', each. And d['a']['x'] can be either 1 or 2 or
>> 3. Does anybody know a convenient (and fast) way to permute over all
>> possible nested dicts like
>> {'a': {'x':1, 'y':4},
>> 'b': {'x':7, 'y':10}}
>> and
>> {'a': {'x':2, 'y':4},
>> 'b': {'x':7, 'y':10}}
>> and so forth?
>>
>> Any link or snippet is appreciated.
>>
>> TIA
>> Christian

>
> def cases(d) :
> import re
> bits = re.split('(\[.*?\])',repr(d))
> vv = [('_%s' % k, ' for _%s in %s' % (k,v))
> for k,v in enumerate(bits[1::2])]
> expr = [p+v for p,(v,_) in zip(bits[::2],vv)]+bits[-1:]+[v for _,v
> in vv]
> return eval('(%s)' % ''.join(expr))


That's too ugly; here is a simpler version, same behav and caveats.

def cases(d) :
import re
d = repr(d)
k,n = 1,1
while n :
d,n = re.subn('\\[(.*?)\\](.*)',
'_%s \\2 for _%s in (\\1,)' % (k,k),
d,1)
k+=1
return eval('('+d+')')

>
> for t in cases({'a': {'x':[1,2,3], 'y':[4,5,6]},
> 'b': {'x':[7,8,9], 'y':[10,11,12]}}) :
> print t
>
>
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 10, 'x': 7}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 10, 'x': 8}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 10, 'x': 9}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 11, 'x': 7}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 11, 'x': 8}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 11, 'x': 9}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 12, 'x': 7}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 12, 'x': 8}}
> {'a': {'y': 4, 'x': 1}, 'b': {'y': 12, 'x': 9}}
> {'a': {'y': 4, 'x': 2}, 'b': {'y': 10, 'x': 7}}
> <snip/>
>
> Caveats : (1) assert eval(repr(d))==d
> (2) no square bracket in either keys or values

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
VOIP over VPN over TCP over WAP over 3G Theo Markettos UK VOIP 2 02-14-2008 03:27 PM
Nested Vector Nester Classes are Nested in my Brain Chad E. Dollins C++ 3 11-08-2005 04:46 AM
Permuting using any number of given chars Brian Wakem Perl Misc 1 05-17-2005 10:21 PM
permuting letters and fairy tales Johannes Nix Python 19 11-17-2004 10:47 PM
Nested iterators (well, not nested exactly...) Russ Perry Jr Java 2 08-20-2004 06:51 PM



Advertisments