Algorithm to make all combinations of items from N buckets where only 1 item can come from each bucket

user_2300211 0
Viewed 81

Given a set of buckets make all combinations, where only 1 element can come from each bucket.

For example, given the 3 buckets:

[
    [1,2],
    ["a","b"],
    ["x"]
]

it would return:

[
    [1], [2], ["a"], ["b"], ["x"],
    [1, "a"], [1, "b"], [1, "x"], [2, "a"], [2, "b"], [2, "x"], ["a", "x"], ["b", "x"],
    [1, "a", "x"], [1, "b", "x"], [2, "a", "x"], ["2", "b", "x"] 
]
combinations subset algorithm python
2 Answers

One approach using combinations + product:

import pprint
from itertools import product, combinations

data = [
    [1, 2],
    ["a", "b"],
    ["x"]
]

res = []
for i in range(1, len(data) + 1):
    for comb in combinations(data, i):
        for p in product(*comb):
            res.append(list(p))

pprint.pprint(res)

Output

[[1],
 [2],
 ['a'],
 ['b'],
 ['x'],
 [1, 'a'],
 [1, 'b'],
 [2, 'a'],
 [2, 'b'],
 [1, 'x'],
 [2, 'x'],
 ['a', 'x'],
 ['b', 'x'],
 [1, 'a', 'x'],
 [1, 'b', 'x'],
 [2, 'a', 'x'],
 [2, 'b', 'x']]
user_40015920

Overal number of combinations is product of len(bucket[i]) + 1 for all buckets (including empty combination). So you can iterate integers from 1 to this value, and get combination corresponding to each integer. For example, using integer division and modulo to retrieve what items form a combination.

a = [[1, 2],  ["a", "b"],    ["x"]]
p = 1
for x in a:
    p *= len(x)+1
for i in range(1, p):
    comb = []
    t = i
    for j in range(len(a)):
        idx = t % (len(a[j]) + 1)
        if (idx):
            comb.append(a[j][idx-1])
        t //= (len(a[j]) + 1)
    print(comb)

Another variant: add special value to every sublist, get itertools.product, remove special values from resulting lists.

import itertools
a = [[1, 2], ["a", "b"], ["x"]]
b = [x + [None] for x in a]
for x in list(itertools.product(*b)):
    print([t for t in x if t])  #rejects zeros but you can see an idea
user_8444160
Related