Python – How to generate every possible way a list of 12 items can be split into 3 lists of any size (including empty)

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.

>Solution :

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)