I need to create a list of all possible sets of 4 groups of 3 numbers, so each group set would have 12 numbers (4 * 3 = 12). For example, with the numbers
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
one possible set is
((1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12))
and another is
((4, 3, 6), (1, 5, 7), (2, 8, 11), (9, 10, 12))
so these two sets should be inside the permutations array. The permutations array should look like
(((4, 3, 6), (1, 5, 7), (2, 8, 11), (9, 10, 12)), (((1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12)), ...)
and the "..." means that there are many more group sets, of course.
However, order does matter. Because of this,
((6, 4, 3), (7, 1, 5), (11, 2, 8), (9, 12, 10))
and
((9, 10, 12), (2, 11, 8), (1, 7, 5), (3, 6, 4))
are both the same as
((4, 3, 6), (1, 5, 7), (2, 8, 11), (9, 10, 12))
Specifically, if the ordering of the groups or the ordering of the things inside the groups are different, it is still the same set of groups.
One way to do this is to do 12 nested for loops (3 * 4 = 12), but I am looking for using a built-in function instead. Can someone please help?
Note: I put parenthesis making the parenthesis array 2-dimensional tuples and each group set a 1-dimensional tuple, but it does not necessarily have to be a tuple. It can be a list, list[tuple], tuple[list], etc.
Note 2: I want a time complexity of at most O(N!), where in this case, N = 12.
Note ∞: This is to solve Balanced Teams.
This is one approach: use itertools.combinations to cut stuff in half, and then use it again to cut those halves in half.
from itertools import combinations, product
def splittings(numbers):
numbers = frozenset(numbers)
assert len(numbers) == 12
result = set()
for AB in map(frozenset, combinations(numbers, 6)):
CD = numbers - AB
first_half_splittings = []
for A in map(frozenset, combinations(AB, 3)):
B = AB - A
first_half_splittings.append((A, B))
second_half_splittings = []
for C in map(frozenset, combinations(CD, 3)):
D = CD - C
second_half_splittings.append((C, D))
for A_B, C_D in product(first_half_splittings, second_half_splittings):
result.add(frozenset(A_B + C_D))
return [tuple(map(tuple, splitting)) for splitting in result]
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
for split in splittings(numbers):
print(split)
This ends up over-counting each splitting 4!=24 times, but that can be resolved using a set of frozensets.
There are probably more optimizations that could be had here, for example, always assigning the first value to the first bin, and then splitting the remaining 11 into 5+6. But this should be a decent starting point.
Edit: here is an implementation of such an optimization, and it makes things a bit easier to understand IMO.
from itertools import combinations, product, starmap
from operator import add
def pair_splittings(numbers, k):
n0, *rest = numbers
rest = frozenset(rest)
for B in combinations(rest, len(numbers) - k):
A = (n0,) + tuple(rest - frozenset(B))
yield (A, B)
def splittings(numbers):
assert len(numbers) == 12
for AB, CD in pair_splittings(numbers, 6):
first_halves = pair_splittings(AB, 3)
second_halves = pair_splittings(CD, 3)
half_choices = product(first_halves, second_halves)
yield from starmap(add, half_choices)
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
for split in splittings(numbers):
print(split)
Edit2: an even more general solution, generalizing to different numbers of bins.
from itertools import combinations, product, starmap
from operator import add
def pair_splittings(numbers, k):
n0, *rest = numbers
rest = frozenset(rest)
for B in combinations(rest, len(numbers) - k):
A = (n0,) + tuple(rest - frozenset(B))
yield (A, B)
def splittings(elements, num_bins):
assert len(elements) % num_bins == 0
bin_size = len(elements) // num_bins
if num_bins == 1:
yield (tuple(elements),)
return
k = num_bins // 2
for half1, half2 in pair_splittings(elements, k*bin_size):
# Option 1: a little bit eager. ##############################
# Here, product() stores both sequences that it's
# iterating through. This is much faster than re-computing
# half2_splittings over and over. Note that storing both
# halves is much less memory than storing their entire product,
# so this is still somewhat lazy.
half1_splittings = splittings(half1, k)
half2_splittings = splittings(half2, num_bins-k)
half_choices = product(half1_splittings, half2_splittings)
yield from starmap(add, half_choices)
# Option 2: extra-lazy. ##############################
# If you're dealing with bigger numbers and minimal memory,
# this might be a better aproach.
# for choices1 in splittings(half1, k):
# for choices2 in splittings(half2, num_bins-k):
# yield choices1 + choices2
for x in splittings(range(12), 4):
print(x)