CODEWITHSUNDEEP
python
Jakob
Jakob

Reputation: 58

Find All Permutations of a List of Dicts

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!

Upvotes: 3

Views: 157

Answers (3)

Pychopath
Pychopath

Reputation: 1580

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

Upvotes: 5

constantstranger
constantstranger

Reputation: 9379

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}

Upvotes: 1

Samwise
Samwise

Reputation: 71562

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}

Upvotes: 3

Related Questions