permuting over nested dicts?

Discussion in 'Python' started by Christian Meesters, Oct 31, 2007.

  1. 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
    Christian Meesters, Oct 31, 2007
    #1
    1. Advertising

  2. Christian Meesters

    Paddy Guest

    On Oct 31, 5:21 pm, 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


    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.
    Paddy, Oct 31, 2007
    #2
    1. Advertising

  3. Christian Meesters

    Anand Guest

    On Oct 31, 10:21 pm, 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.
    >


    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, Nov 1, 2007
    #3
  4. Christian Meesters

    Anand Guest

    On Nov 1, 2:12 pm, Anand <> wrote:
    > On Oct 31, 10:21 pm, 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.

    >
    > 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
    Anand, Nov 1, 2007
    #4
  5. Christian Meesters

    Ant Guest

    On Nov 1, 9:12 am, Anand <> wrote:
    ....
    > This code works for dictionaries of any nested level.


    At least up to the max recursion depth.

    --
    Ant.
    Ant, Nov 1, 2007
    #5
  6. 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
    Christian Meesters, Nov 1, 2007
    #6
  7. Christian Meesters

    Boris Borcic Guest

    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
    Boris Borcic, Nov 1, 2007
    #7
  8. Christian Meesters

    Paddy Guest

    On Nov 1, 10:51 am, Christian Meesters <> 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.
    Paddy, Nov 6, 2007
    #8
  9. Christian Meesters

    Boris Borcic Guest

    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
    Boris Borcic, Nov 8, 2007
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Afanasiy

    Add two dicts

    Afanasiy, Aug 29, 2003, in forum: Python
    Replies:
    12
    Views:
    590
    John Roth
    Aug 30, 2003
  2. Johannes Nix

    permuting letters and fairy tales

    Johannes Nix, Nov 11, 2004, in forum: Python
    Replies:
    19
    Views:
    561
    Steven Bethard
    Nov 17, 2004
  3. Kenneth Dombrowski

    cPickle segfault with nested dicts in threaded env

    Kenneth Dombrowski, Sep 8, 2010, in forum: Python
    Replies:
    3
    Views:
    253
    Kenneth Dombrowski
    Sep 9, 2010
  4. bruce
    Replies:
    0
    Views:
    244
    bruce
    Jan 10, 2012
  5. Brian Wakem

    Permuting using any number of given chars

    Brian Wakem, May 17, 2005, in forum: Perl Misc
    Replies:
    1
    Views:
    76
    Anno Siegel
    May 17, 2005
Loading...

Share This Page