pythongroupingpermutationbuilt-ingroup# All Grouping Permutations Built-in Functions

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.

Solution

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)
```

- AttributeError: install_layout when attempting to install a package in a virtual environment
- Python list comprehension - want to avoid repeated evaluation
- Hash algorithm for dynamic growing/streaming data?
- matplotlib - making labels for violin plots
- Python How to I check if last element has been reached in iterator tool chain?
- Polars and the Lazy API: How to drop columns that contain only null values?
- Why are my Mean, Var, and Std outputs from NumPy different from what the online grader expects?
- Correlation dataframe convertion from results from pl.corr
- Polars DataFrame transformation
- Discord rate limiting while only sending 1 request per minute
- Check if column contains (/,-,_, *or~) and split in another column - Pandas
- How to draw a rectangle at (x,y) in a PyQt GraphicsView?
- how to calculate correlation between ten columns with polars
- How to set class attribute with await in __init__
- Detect hindi encoding, response received from Facebook API in Python
- Is it possible to write a horizontal if statement with a multi-line body?
- Max length of items in list
- Cannot subclass multiprocessing Queue in Python 3.5
- How can I get notified of updates to Python packages in a unified way?
- Using python AST to traverse code and extract return statements
- merge groups of columns in a polars dataframe to single columns
- Group Pandas DataFrame by Continuous Date Ranges
- Flask login @login_required not working
- Odoo: one2many and many2one? KeyError:'___'
- merge some columns in a Polars dataframe and duplicate the others
- Python: Create table from string mixed with separators using FOR loops
- How do I type hint a method with the type of the enclosing class?
- How can I verify an emails DKIM signature in Python?
- Writing a class that accepts a callback in Python?
- Python Paramiko channel.exec_command not returning output intermittently