Python - How to generate every possible way a list of 12 items can be split into 3 lists of any size-CodePudding

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.