From Suitcases to Supercomputers: The Hidden Art of Splitting Things Up

📚 This article is part of our Algorithmic Journeys series — highlighting experiments, benchmarks, and exploring the quirks of algorithms.

Originally published on Medium.

Ever packed your suitcase for a trip and thought, “What’s the best way to group my stuff?” That innocent question — how to group a set of items — is the heartbeat of a surprisingly deep mathematical problem: set partitioning.

Whether you’re clustering data, organizing work shifts, or distributing goods into packages, set partitions silently power many real-life logistics and algorithmic decisions.

I got a chance to dive headfirst into this world — not just to understand it, but to make it faster!

Real-Life Set Partitions: Packing the Problem

Set partitions are just ways to divide a collection into non-overlapping, non-empty subsets. For example, for the set {1, 2, 3}, all valid partitions are:

{1}, {2}, {3}    
{1}, {2, 3}
{1, 2}, {3}
{1, 3}, {2} 
{1, 2, 3}

This isn’t just math class. Think:

• Grouping employees into teams
• Segmenting customers
• Packing goods into containers

Each valid combination is a partition. And when you realize how many combinations are possible, things get real. Press enter or click to view image in full size Photo by YummyBuum on TheHungryJPEG

How Many Are There?

The number of set partitions for a set of size n is given by the Bell numbers:

B(1) = 1, B(2) = 2, B(3) = 5, B(4) = 15, B(5) = 52, …, B(10) = 115975.

You can see how fast it explodes. By the time we hit 15 elements, we’re looking at over 1.3 billion partitions. So the need for efficient algorithms is not just academic — it’s essential.

Recursive vs. Non-Recursive: Beauty vs. Beast Mode

If you’ve taken an algorithms class, you’ve probably written a recursive function to generate some sets. It’s elegant, readable, and theoretically satisfying.

But when it comes to speed, recursion often falls flat. Why? The main reason is that recursion creates stack overhead, which slows down the execution of the program.

That’s where non-recursive algorithms enter — unromantic, sometimes harder to read, but blazing fast. They favor iteration, state machines, and clever index tricks.

Benchmarking Algorithms in Python and C

My job was to compare four algorithms for generating all set partitions for a given set size:

• Hutchinson’s (Published 1963)
• Semba’s (Published 1984)
• Er’s (Published 1987)
• Djokic et al.’s (Published 1989)

Djokic’s is theoretically stated as faster than Er’s which is faster than Semba’s which is followed by Hutchinson’s. This follows our intuition as algorithms are supposed to get faster over time.

I implemented them in Python for clarity and then in C to really push performance boundaries, which, let’s just say . . . complicated things.

Each implementation was benchmarked on:

• Total CPU time (how long just the CPU took to execute each algorithm, generating all set partitions, irrespective of other confounding time variables involved)
• Scalability to large n

Python indicated that Djokic was the fastest, Hutchinson was the slowest, and Semba and Er seemed pretty close to each other (with Semba a bit faster), which almost follows what was previously stated in their papers except for Semba and Er.

C is where things get weird and a tad bit inconsistent, which is why we benchmarked them in the cloud (Google’s servers), on Windows OS, and on Linux OS. For each we either toggled the C compiler’s optimization or didn’t. If the C optimizer is toggled it makes a bunch of optimizations in Assembly code (machine code) that are extremely difficult for humans to understand, which we don’t need to worry about here! Here are the results!

In the Cloud, when the optimizer was toggled, the results pretty much exactly followed what we expect. The fastest was Djokic which was followed by Er then Semba followed by Hutchinson. Yay, going well so far! However, with the optimizer turned off Semba was actually the fastest! What! This was weird, so we tested on Windows and Linux in order to discover the truth. Who wins, the tortoise or the hare? The results on Windows are as follows.

Windows seemed to confirm our suspicion that when the C compiler was unoptimized, Semba was the fastest, while Djokic took the lead with the optimizer on. These results were consistent on Linux as well!

What can we conclude?

One thing we can state is that Djokic is not always the fastest. In this way the published paper is not completely correct. The algorithm speeds depend on whether you are using the C optimizer or not. If you are not, Semba seems to take the lead. However, practically you should always use the optimizer because you always want faster runtime. In this way, practically Djokic is the fastest.

Try it Yourself

Want to explore the code? Tinker with the benchmarks? Clone the github repo at https://github.com/unatech-labs/set_partitions and go wild!

Research Done Right

This work was part of a research internship at Unatech, where I had the freedom to dive deep, benchmark aggressively, and nerd out on partitions for weeks. Big thanks to Alexander Pikovski for letting me explore.

If you’re into clean algorithmic work with real-world applications — this is your sign to explore the world of set partitions. It’s messier, faster, and more beautiful than you might think.

📚 This article is part of our Algorithmic Journeys series — highlighting experiments, benchmarks, and exploring the quirks of algorithms.

Originally published on Medium.

Find more at https://research.unatech.co.