-1

Assume I have a dictionary with any number of elements, for example here we have 3 elements.

{'key1':[1,2], 'key2':[3,4,5], 'key3':[6,7]}

I want to take one number at time from each list in the dictionary to generate this list:


[[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]]

How to perform this type of recursion in python?

Reem
  • 107
  • 1
  • 7

4 Answers4

2

How about using itertools.product:

>>> import itertools
>>> d = {'key1': [1, 2], 'key2': [3, 4, 5], 'key3': [6, 7]}
>>> [list(t) for t in itertools.product(*d.values())]
[[1, 3, 6], [1, 3, 7], [1, 4, 6], [1, 4, 7], [1, 5, 6], [1, 5, 7], [2, 3, 6], [2, 3, 7], [2, 4, 6], [2, 4, 7], [2, 5, 6], [2, 5, 7]]
>>> # You can do this manually using three nested loops:
>>> [[a, b, c] for a in d['key1'] for b in d['key2'] for c in d['key3']]
[[1, 3, 6], [1, 3, 7], [1, 4, 6], [1, 4, 7], [1, 5, 6], [1, 5, 7], [2, 3, 6], [2, 3, 7], [2, 4, 6], [2, 4, 7], [2, 5, 6], [2, 5, 7]]
Sash Sinha
  • 18,743
  • 3
  • 23
  • 40
1
import itertools as it

foo = {'key1':[1,2], 'key2':[3,4,5], 'key3':[6,7]}
list(it.product(*foo.values()))

Produces:

[
  (1, 3, 6),
  (1, 3, 7),
  (1, 4, 6),
  (1, 4, 7),
  (1, 5, 6),
  (1, 5, 7),
  (2, 3, 6),
  (2, 3, 7),
  (2, 4, 6),
  (2, 4, 7),
  (2, 5, 6),
  (2, 5, 7),
]
Kache
  • 15,647
  • 12
  • 51
  • 79
0

Without using itertools, you could use a function to iterate through the values of the current key, append each value to the combination and call itself with the updated combination and the next index.

def generate_permutations(d: dict):
    keys = list(d.keys())
    result = []

    def backtrack(combination, idx):
        if idx == len(keys):
            result.append(combination)
            return
        
        key = keys[idx]
        for val in d[key]:
            new_combination = combination + [val]
            backtrack(new_combination, idx + 1)
    
    backtrack([], 0)
    return result

d = {'key1': [1, 2], 'key2': [3, 4, 5], 'key3': [6, 7]}
permutations = generate_permutations(d)
print(permutations)

I'd prefer the itertools version, it's much shorter, but this version could be more comprehensible.

nadine
  • 92
  • 8
0
import itertools

my_dict = {'key1': [1, 2], 'key2': [3, 4, 5], 'key3': [6, 7]}
result = [list(comb) for comb in itertools.product(*my_dict.values())]

print(result)

The itertools.product function is used to generate the Cartesian product of the values in the dictionary. By passing *my_dict.values() as arguments, it unpacks the values as separate arguments to the function. Each element of the resulting Cartesian product is then converted to a list using a list comprehension.

saidtheflux
  • 26
  • 3