Find All Permutations of a List of Dicts

Question

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!

Answer 1

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}

Answer 2

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}