On Nov 1, 2:12 pm, Anand <[EMAIL PROTECTED]> wrote: > On Oct 31, 10:21 pm, Christian Meesters <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list