permuting over nested dicts?

[Anand]

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