# Algorithm to return all possible ways to divide n unique elements into groups of size k

If I have as set N of n unique elements, is there a known algorithm that can return every possible way in which they can form groups of size k?

Eg: If N = { A, B, C, D} and k = 2, then the algorithm should return

[[(A, B), (C, D)],
[(A, C), (B, D)],
[(A, D), (B, C)]]


Here it's safe for me to assume that n is always divisible by k! :D

Bonus: Is there a library to do this in Python?

The algorithm is straight-forward once you decide on the order of the subsets in the partitions. A simple algorithm produces partitions where:

• each subset in the partition is generated in order
• the subsets themselves are in order by their first element

These partitions can be produced recursively, adding each element of the set in turn to a partition of the initial elements where the partition components have at most $$k$$ elements. Such a partition can be extended with a new element by:

• adding the new element to one of the existing components, if that component has fewer than $$k$$ elements, or
• adding a new component at the end of the partition, if the partition doesn't already have $$n/k$$ components.

The same algorithm, without the check for the size of the partition element, could be used to generate all partitions.

You're unlikely to find this in a standard Python library, but I'm sure other implementations exist. In any event, this is not the right place to ask about software libraries in existing languages.

Here's the above algorithm written in Python. Unlike a functional version, this uses a state variable containing a mutable partial partition; each modification is undone after the recursive call, and the partitions finally produced are copied in order to avoid surprises.

def part(s, k):
"""Yields each partition of s into subsets of size k, which must be a
divisor of len(s).
"""

def step(i):
if i == len(s):
# Deep copy the current partition
yield list(list(p) for p in part)
else:
for p in part:
if len(p) < k:
p.append(s[i])
yield from step(i + 1)
p.pop()
if len(part) * k < len(s):
part.append(list(s[i]))
yield from step(i + 1)
part.pop()

part = []
yield from step(0)


In theory you could do this using a combinations generator, such as the one in the itertools:

(Pseudocode)
partitions(Seq, K) is
if length(Seq) == K:
return a single partition with Seq as its only component.
otherwise:
# Length must be > K; otherwise it wasn't a multiple of K to start with
for each combination C of Seq of length K which includes Seq[0]:
for each Partition in partitions(Seq - C, K):  (***)
prepend C to Partition and add it to the list to result


Note the line (***) which requires both a combination C and the list of other elements of Seq, ideally in order. There's no particularly easy way to get that out of itertools.combinations,

• To be fair, when $k=n/2$, the partitions can be trivially derived from the set of combinations which include the first element; if you flatten the list of partitions, you get the list of combinations. This is not true for other values of $k$, although there is a recursive algorithm which uses itertools.combinations as a subfunction, not very efficiently. Maybe I'll add that, along with the non-recursive solution which is on SO somewhere.
– rici
Commented Aug 16, 2021 at 20:39
• Thanks for the answer, I'll try it out now. Also, could you tell me where I can find the algorithm using itertools.combinations that you mentioned here in the comment? :) Edit: I forgot to mention in the question that the order of items in the subsets doesn't matter! Commented Aug 17, 2021 at 9:40
• @user6714507: If the order mattered, my algorithm wouldn't work. It's because the order doesn't matter than I can choose a canonical order. That's important.
– rici
Commented Aug 17, 2021 at 18:24

Here's Python code to do what you want fairly efficiently. It seems similar to rici's answer, but I didn't read through their answer to write this.

from typing import Set, List
from itertools import combinations

def group_iterator(s: Set, k: int) -> List[Set]:
assert len(s) % k == 0, f"Set of size {len(s)} cannot be evenly split into groups of size {k}"
# how many groups there are
t = len(s) // k
if t == 1:
yield [s]
return
# get a random item from the set
first_item = next(iter(s))
# take out that first item so we don't use it again
rest_of_elements = s - {first_item}
# go through all the possible ways of getting the other items for this group
for rest_of_group in combinations(rest_of_elements, k - 1):
# go from the default tuple back into a set
rest_of_group = set(rest_of_group)
# add the first item back into the group
group = {first_item} | rest_of_group
# repeat recursively for the other groups
# there will be no overlap with this group, because this is the only group that has this particular first item
for other_groups in group_iterator(rest_of_elements - rest_of_group, k):
yield [group] + other_groups


You can test it with:

for thing in group_iterator(set(["A", "B", "C", "D"]), 2):
print(thing)


Output:

[{'C', 'A'}, {'B', 'D'}]
[{'C', 'D'}, {'A', 'B'}]
[{'C', 'B'}, {'A', 'D'}]


Please note that my type hinting is not 100% correct, but it doesn't really matter; it's just there to help people see the general form of the input and output. Fairly certain Mypy would not be happy with this in many different ways.

• Thanks for your detailed answer. I wanted to let you know that we discourage answers that are only or mostly a block of code. We're not a coding site. We'd prefer to see ideas, explanation, justification, and/or concise pseudocode. Perhaps you could edit your answer to provide explanation, in a way that would help someone even if they don't know how to read Python?
– D.W.
Commented Aug 30, 2022 at 3:52
• Ah, that makes sense. I think every line in the code is commented so you can pretty much tell what it does regardless of the language (I even commented set addition, etc.). Forgot this wasn't Stack Overflow. Unfortunately, I think this will mostly be one of those answers that doesn't fit super well with the site, but will probably help people who come here; this was the only question I could find on this online, and I came here looking for code. Is there a better way to handle this? Should I self-answer a new question on Stack Overflow with this as the answer? Commented Aug 30, 2022 at 20:58