I have 2 lists, one with 12 elements and one with 3 sub-lists.
a = [1,2,3,4,5,6,7,8,9,10,11,12]
b = [[],[],[]]
I need to write Python code which will generate every possible way in which the 12 elements in a can be distributed across the sub-lists in b. There are 3^12 (just over half a million) combinations. For example, some possible combinations would be the following:
[[1,2,3,4,5,6,7,8,9,10,11,12],[],[]]
[[1,2,3,4],[5,6],[7,8,9,10,11,12]]
[[1,4,12],[2,3,9,11],[5,6,7,8,10]]
Order does not matter within the lists. I've tried using some itertools functions such as permutation and combination but they don't seem to do what I'm looking for. I tried
buildings = list(range(1,13)) #assign each building a unique id
building_arrangement = [list(range(1,13)),[],[]] # quarries, factories, markets
all_arrangements.append(building_arrangement)
combos = itertools.combinations(buildings, 3)
for combo in combos:
print(combo)
But the above seems to get the combination of each of the 12 numbers individually as opposed to treating the full 12 numbers as a set and finding each unique set that can be made. I'm not sure if this can be done via any pre-existing libraries, itertools doesn't seem to provide a way to do this from what I can see in the documentation, but I could be wrong.
CodePudding user response:
Note that each combination can be encoded by an m-ary number, where m is the number of sublists. Iterating over all n-digit m-ary numbers (where n is the number of elements) will do the trick:
N = 12
M = 3
for n in range(N**M):
combination = [[] for __ in range(M)]
for i in range(N):
combination[n // 3**i % 3].append(i)
print(combination)
CodePudding user response:
You can use a recursive generator function:
a = [1,2,3,4,5,6,7,8,9,10,11,12]
def groups(d, n, c = []):
if not d and len(c) == n:
yield c
elif d:
for i, j in enumerate(d):
if not c or len(c) 1 <= n:
yield from groups(d[:i] d[i 1:], n, c [[j]])
if c:
yield from groups(d[:i] d[i 1:], n, c[:-1] [[*c[-1], j]])
def results(d, n):
s = []
for i in groups(d, n):
if (k:=[*map(sorted, i)]) not in s:
yield k
s.append(k)
r = results(a, 3)
for _ in range(10): #first 10 results
print(next(r))
Output:
[[1], [2], [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3], [4, 5, 6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4], [5, 6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5], [6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7], [8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8], [9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8, 9], [10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [12]]
CodePudding user response:
Also why not try itertool recipes, powerset()
pip install more-itertools
Then,
from more_itertools import recipes
a = [1,2,3,4,5,6,7,8,9,10,11,12]
tuples = recipes.powerset(a)
for tuple in tuples:
print(tuple)
This will create all possible sets from the iterable given to it. You can divide it in to lists of 3 using a different funtion.