permuting over nested dicts?

[Christian Meesters]

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

 

[Paddy]

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/Cookbook/Python/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.

 

[Anand]

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))

 

[Anand]

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

 

[Ant]

This code works for dictionaries of any nested level.

At least up to the max recursion depth.

 

[Christian Meesters]

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

 

[Boris Borcic]

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

 

[Paddy]

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.

 

[Boris Borcic]

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