CODEWITHSUNDEEP
pythonmath
wei2912
wei2912

Reputation: 6619

Obtaining the combination of elements in a dictionary

I have a dictionary that looks like this:

a: [a]
b: [b, c]
c: [d, e, f]

The number of keys and the number of elements in each list is unknown beforehand.

I would like to be able to obtain all the possible combinations of the elements in every list. The output for the above dictionary would be something like this:

[a, d, b]
[a, e, c]
[a, f, b]
[a, d, c]
[a, e, b]
[a, f, c]

Order for both the lists in the list and the elements in the lists in the list (that's a mouthful) doesn't matter.

I tried a solution which I have posted an answer to, but I am curious to find out if there are more efficient solutions.

EDIT: Only one element can be taken from every key in the dictionary. Following the example above, you can't have [b d e] as d e is from c.

Upvotes: 1

Views: 89

Answers (2)

Deck
Deck

Reputation: 1979

Well. I understand the question and corrected my answer.

Make the list of values using list comprehension

>>> d = {"a": [1], "b": [2,3], "c": [4,5,6]}
>>> values = [v for k,v in d.items()]
>>> values
[[1], [4, 5, 6], [2, 3]]

Then use itertools.product which is equivalent to for-loop.

>>> for i in itertools.product(*l):
...     print i
... 
(1, 4, 2)
(1, 4, 3)
(1, 5, 2)
(1, 5, 3)
(1, 6, 2)
(1, 6, 3)

Upvotes: 3

wei2912
wei2912

Reputation: 6619

I came up with this:

def _gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

def _lcm(a, b):
    return a * b // _gcd(a, b)

def lcm(numbers):
    return reduce(_lcm, numbers)

def combinations(dict):
    lengths = []
    for key in dict.keys():
        lengths.append(len(dict[key]))

    lcm_int = lcm(lengths)
    for key in dict.keys():
        values = []
        length = len(dict[key])
        for i in range(lcm_int):
            values.append(dict[key][i%length])
        dict[key] = values

    combinations = []
    for i in range(lcm_int):
        values = []
        for key in dict.keys():
            values.append(dict[key][i])
        combinations.append(values)
    return combinations

This code finds the LCM of the lengths of all lists in the dictionary. It then expands each list to something like this:

[a]       -> [a, a, a, a, a, a]
[b, c]    -> [b, c, b, c, b, c]
[d, e, f] -> [d, e, f, d, e, f]

Afterwards, it takes the first element of every list and places it in a new list (a combination) and does the same for the rest of the elements.

Upvotes: 0

Related Questions