permuting over nested dicts?

[Anand]

On Nov 1, 2:12 pm, Anand <anandol... at gmail.com> wrote:
> On Oct 31, 10:21 pm, Christian Meesters <meest... at uni-mainz.de> 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