Expand the following dictionary into following list

Question

how to generate the following list from the following dictionary

d = {2: 4, 3: 1, 5: 3}

f = [
    2**1,2**2, 2**3, 2**4, 3**1, 5**1, 5**2, 5**3, 
    2**1 * 3, 2**2 * 3, 2**3 * 3, 2**4 * 3, 5**1 * 3, 5**2 * 3, 5**3 * 3, 
    2**1 * 5, 2**2 * 5, 2**3 * 5, 2**4 * 5, 
    2**1 * 5**2, 2**2 * 5**2, 2**3 * 5**2, 2**4 * 5**2, 3**1 * 5**2, 
    2**1 * 5**3, 2**2 * 5**3, 2**3 * 5**3, 2**4 * 5**3, 3**1 * 5**3, 
    2**1 * 3**1 * 5**1, 2**1 * 3**1 * 5**2, 2**1 * 3**1 * 5**3, 
    2**2 * 3**1 * 5**1, 2**2 * 3**1 * 5**2, 2**2 * 3**1 * 5**3, 
    2**3 * 3**1 * 5**1, 2**3 * 3**1 * 5**2, 2**3 * 3**1 * 5**3, 
    2**4 * 3**1 * 5**1, 2**4 * 3**1 * 5**2, 2**4 * 3**1 * 5**3, 
    ]

Moreover I want to expand for more general case ie dictionary of k key-value pairs

Edit: Explanation of the pattern: Each key is raised to power of 0 to it's value and after that for each of those terms we do combination with similar terms from other keys.

I can think of doing so in recursive ways. Any non recusive approach is welcome.

PS: Order is not important

Can you explain the pattern? See how to create a [mcve]. What's preventing you from solving the problem yourself? Edit the question. — Peter Wood, May 07 '22 at 15:43
Why does the list contain both `5**1 * 3` and `3**1 * 5`? That's the same number. — Kelly Bundy, May 07 '22 at 15:59
@KellyBundy sorry my bad fixed it. but duplicate generation in not much of a concern for me, we can anytime dedup if necessary. — ishandutta2007, May 07 '22 at 16:05

Kelly Bundy · Answer 1 · 2022-05-07T23:02:33.260

6

One way, expanding the list with each possible factor and its powers:

f = [1]
for k, v in d.items():
    f += [x * k**i
          for x in f 
          for i in range(1, v+1)]

Perhaps faster, repeatedly multiplying with the factor instead of computing powers:

f = [1]
for k, v in d.items():
    g = f
    for _ in range(v):
        g = [x * k for x in g]
        f += g

Somewhat tricky version of that which is short and I believe fast (confirmed by OP in the comments):

from itertools import islice, repeat
from operator import mul

f = [1]
for k, v in d.items():
    f += map(mul, repeat(k, len(f) * v), f)

A completely different way, first computing the powers for each factor and then using itertools.product and math.prod to combine them:

from itertools import product, accumulate, repeat
from math import prod

f = list(map(prod, product(*[[k**i for i in range(v+1)]
                             for k, v in d.items()])))

All include the number 1 in the list. If that's a problem, just remove it.

edited May 07 '22 at 23:02

answered May 07 '22 at 16:08

Kelly Bundy

23,480
7
29
65

awesome . thanks a lot . you should mention , last one works on python 3.8+. – ishandutta2007 May 07 '22 at 16:15
2

@BobMcCheese Meh, 3.8 is over 2.5 years old by now, so I don't feel like pointing that out anymore :-) – Kelly Bundy May 07 '22 at 16:18
2

3rd one is the winner in speed. Here are the time for some larger v,` 7.25 2.80 2.08 6.45` – ishandutta2007 May 07 '22 at 16:51
1

@BobMcCheese Thanks for measuring. Looks like what I suspected (though I really couldn't tell where the last one would fall, as it's so different). – Kelly Bundy May 07 '22 at 17:00

Expand the following dictionary into following list

1 Answers1

Linked