Find All Permutations of a List of Dicts

user_6068598 0
Viewed 78

So I have a list of dicts containing letters and their frequencies.

letter_freq = [
   {'a': 10, 'b': 7},
   {'d': 15, 'g': 8},
   {'a': 12, 'q': 2}
]

I want to find all possible combinations of these dictionaries, as well as the total of their values:

perms = {
   'ada': 37, 'adq': 27, 'aga': 30, 'agq': 20, 'bda': 34, 'bdq': 24, 'bga': 27, 'bgq': 17
}

I've looked at itertools.product(), but I don't see how to apply that to this specific use case. My intuition is that the easiest way to implement this is to make a recursive function, but I'm struggling to see how to add the values and the strings for the keys and make it all work.

Also, this list and the dicts can be of any length. Is there a simple way to do this that I haven't found yet? Thank you!

python
3 Answers

Solutions and Benchmark:

Yes, itertools.product works:

from itertools import product

perms = {
    ''.join(keys): sum(vals)
    for prod in product(*map(dict.items, letter_freq))
    for keys, vals in [zip(*prod)]
}

Alternatively, build the products for the keys and the values separately, so we don't have to separate them:

perms = {
    ''.join(keys): sum(vals)
    for keys, vals in zip(product(*letter_freq),
                          product(*map(dict.values, letter_freq)))
}

Or fully separate their constructions (my favorite one):

keys = map(''.join, product(*letter_freq))
vals = map(sum, product(*map(dict.values, letter_freq)))
perms = dict(zip(keys, vals))

Benchmark would be interesting, I suspect my last one will be fastest of these and also faster than Samwise's.

Yet another, inspired by a glance at constantstranger's (but much faster than theirs in some initial benchmark):

items = [('', 0)]
for d in letter_freq:
    items = [(k0+k, v0+v)
             for k, v in d.items()
             for k0, v0 in items]
perms = dict(items)

Benchmark:

With your example list of dicts:

  6.6 μs  perms1
  4.5 μs  perms2
  4.1 μs  perms3
  4.0 μs  perms4
 11.0 μs  perms_Samwise
 12.7 μs  perms_constantstranger

With a list of seven dicts with four items each:

 15.5 ms  perms1
  7.6 ms  perms2
  5.5 ms  perms3
  4.8 ms  perms4
 27.2 ms  perms_Samwise
 42.2 ms  perms_constantstranger

Code (Try it online!):

def perms1(letter_freq):
    return {
        ''.join(keys): sum(vals)
        for prod in product(*map(dict.items, letter_freq))
        for keys, vals in [zip(*prod)]
    }

def perms2(letter_freq):
    return {
        ''.join(keys): sum(vals)
        for keys, vals in zip(product(*letter_freq),
                              product(*map(dict.values, letter_freq)))
    }

def perms3(letter_freq):
    keys = map(''.join, product(*letter_freq))
    vals = map(sum, product(*map(dict.values, letter_freq)))
    return dict(zip(keys, vals))

def perms4(letter_freq):
    items = [('', 0)]
    for d in letter_freq:
        items = [(k0+k, v0+v)
                 for k, v in d.items()
                 for k0, v0 in items]
    return dict(items)

def perms_Samwise(letter_freq):
    return {''.join(k for k, _ in p): sum(v for _, v in p) for p in itertools.product(*(d.items() for d in letter_freq))}

def perms_constantstranger(letter_freq):
    stack = [['', 0]]
    [stack.append((stack[i][0] + k, stack[i][1] + v)) for row in letter_freq if (lenStack := len(stack)) for k, v in row.items() for i in range(lenStack)]
    return dict(row for row in stack if len(row[0]) == len(letter_freq))

funcs = perms1, perms2, perms3, perms4, perms_Samwise, perms_constantstranger

letter_freq = [
   {'a': 10, 'b': 7, 'c': 5, 'd': 2},
   {'d': 15, 'g': 8, 'j': 6, 'm': 3},
   {'a': 12, 'q': 2, 'x': 1, 'z': 4},
   {'a': 10, 'b': 7, 'c': 5, 'd': 2},
   {'d': 15, 'g': 8, 'j': 6, 'm': 3},
   {'a': 12, 'q': 2, 'x': 1, 'z': 4},
   {'a': 10, 'b': 7, 'c': 5, 'd': 2},
]

from timeit import repeat
import itertools
from itertools import product

expect = funcs[0](letter_freq)
for func in funcs:
    result = func(letter_freq)
    assert result == expect

for _ in range(3):
    for func in funcs:
        t = min(repeat(lambda: func(letter_freq), number=1))
        print('%5.1f ms ' % (t * 1e3), func.__name__)
    print()
user_182384220

itertools.product is indeed what you want.

>>> letter_freq = [
...    {'a': 10, 'b': 7},
...    {'d': 15, 'g': 8},
...    {'a': 12, 'q': 2}
... ]
>>> import itertools
>>> {''.join(k for k, _ in p): sum(v for _, v in p) for p in itertools.product(*(d.items() for d in letter_freq))}
{'ada': 37, 'adq': 27, 'aga': 30, 'agq': 20, 'bda': 34, 'bdq': 24, 'bga': 27, 'bgq': 17}
user_37997590

If for any reason you wanted to roll your own permutations using comprehensions instead of product() and map(), you could do it this way:

        letter_freq = [
           {'a': 10, 'b': 7},
           {'d': 15, 'g': 8},
           {'a': 12, 'q': 2}
        ]       
        stack = [['', 0]]
        [stack.append((stack[i][0] + k, stack[i][1] + v)) for row in letter_freq if (lenStack := len(stack)) for k, v in row.items() for i in range(lenStack)]
        perms = dict(row for row in stack if len(row[0]) == len(letter_freq))
        print(perms)

Output:

{'ada': 37, 'bda': 34, 'aga': 30, 'bga': 27, 'adq': 27, 'bdq': 24, 'agq': 20, 'bgq': 17}
user_181354540
Related