How To The Count Number Of Ways That A List Of Items Can Be Partitioned Into Identical Sized Sub-Sets Ignoring Ordering Of Elements

a.k.a Fun With Combinatorics….

This article was initially meant to be incorporated into another article I wrote about the Wedding Seating Problem .

Building A Wedding Seating Plan Using Probabilistic Methods & Simulated Annealing

Unfortunately the math got a bit much and I wanted to put up a mini-article title that describes exactly what this does to help anyone else with the same problem to easily find a solution.

So the problem statement is “How many ways can a List of M items be partition into EVENLY sized sets of size N ?” The practical example I was applying this to was to figure out how many seating arrangements are possible for a given guest list and set table size (Under the condition that we allow for empty seats i.e if we have 45 pax and 8pax/table, we will need 6 tables and have 3 empty seats)

A quick check on Stack Overflow gave me something close but not exactly what I was looking for

How do you split a list into evenly sized chunks?

It sounded simple enough at first but after trying to ‘reason’ it out with pen and paper, I realized my high school combinatorial math may be a bit rusty.

So I had to back up a bit and pick up a few basic building blocks in terms of counting the number of ways elements can be combined for a given set of constraints…

Combinatorics: permutations, combinations and dispositions

The article above covers these quite well. The TLDR version is that for permutations - order matters and in combinations — they don’t (i.e [A,B,C] is considered same as [C,B,A] is same as [B,A,C]) (For now let’s just ignore dispositions which are just permutations where the number of objects we want to pick is less than the total number of objects)

Now if it was just a simple question of how many ways could you seat a SINGLE table (e.g. nCr where n=45 pax , r=8 pax per table) where we can ignore seating order (i.e doesn’t matter which guest is at which seat at the table) we can calculate it like this:-

import math
def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)
nCr(n,r)

Thankfully for us , this becomes super simple in the latest versions of the math library (Python 3.8 onwards) where there is already a pre-built function math.comb that does the same thing.

math.comb(n,r)

Now the problem is , this sort of calculation tends to take a long time when you get to large numbers so this user on Quora suggested using log numbers to speed up the calculation process

What are the method to calculate nCr in Python for large values of r and n?

def log_fact(n):
    return sum(math.log10(i) for i in range(1, n+1))
def big_nCr(n, r):
    a, b, c = log_fact(n), log_fact(r), log_fact(n-r)
    return 10**(a-b-c)
big_nCr(n,r)

That’s all fine and good but unfortunately for the problem at hand — it’s not just about estimating the combinations possible for a single table — it’s about how many ways could we seat ALL the different guests across ALL the different tables.

Some further digging led me to the interesting concept of Stirling Numbers (of the Second Kind) which is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by S(n,k)

Stirling numbers of the second kind - Wikipedia

Aha! This was it ! The formula was unfortunately not a straightforward one and involves recursive function. Thankfully there were also some implementations online for how to use Python to calculate the Sterling number

Unfortunately looking at the results it was generating , something felt a bit off — if you have 6 items (1,2,,3,4,5,6) and 2 partitions (i.e each partition should be 3 characters each), the Stirling number (of the 2nd kind) came up to 31 which felt like too many…

I found a piece of code that enumerates all the possible sets which was when I realized the uneven sized sub-sets were included in the count.

Stirling Number Of The 2nd Kind For S(6,2) — I was only looking for the red which was 10 of the 31

What I was after should in principle be simpler as I was just looking for only the ones that are evenly sized.

I first started by seeing if I could write a script that filters out all the other sets that do not have identically sized partitions but I got lucky and stumbled upon this StackOverflow article:

Producing all groups of fixed-length combinations

from itertools import combinations
def partitions(s, r):
    s = set(s)
    assert(len(s) % r == 0)
    if len(s) == 0:
        yield ()
        return
    first = next(iter(s))
    rest = s.difference((first,))
    for c in combinations(rest, r - 1):
        first_subset = (first,) + c
        for p in partitions(rest.difference(c), r):
            yield (first_subset,) + p

Using this therefore all I had to do was

NoOfArrangements=len(list(partitions(s,r)))

The only thing bad about this is that it does not scale well — works fine if you are doing something like S=6, r=3 but if you have say 200 guests and 10 tables then it takes forever to run because it is trying to enumerate all the possible arrangements.

I found this other solution here that doesn’t bother with enumerating the answers but just calculates the total no of ways to arrange the sets

Problem : Permutation and Combination : In how many ways can we divide 12 students in groups of…

Since it’s on Maths Stackexchange it’s not Python but the basic idea is that the answer will be given by this equation:-

n! / ((n/k)!*(k!**(n/k))

Turning it into Python…

NoOfCombinations=math.factorial(noOfElements)/((math.factorial(noOfElements/r))*(math.factorial(r)**(noOfElements/r)))

The problem with this approach is that it still ‘breaks’ when the numbers get too large e.g. 200,20 as I got a “OverflowError: int too large to convert to float”

I tried to find another way and figured out that I could estimate the same figure using the following logic

For n , k (n elements and k sized partitions)

No Of Arrangements

= nCr(n-k*(n/k),k) x nCr(n-k*(n/k-1),k)….x nCr(k,k) / (n/k)!

Working it out with numbers of 12,3

nCr(12,3) x nCr(9,3) x nCr(6,3) x nCr(3,3) / (12/3)! = 15400

The rationale is that for the first compartment, you have 12 elements to choose from to fill the 3 slots, in the second compartment you have 9 elements left to fill 3 slots and so on until the end. We divide by 12/3! to eliminate the duplicate arrangements.

Writing this out in code gives:-

noOfElements=240
r=12
list_for_nCr=[]
for i in range(0,int(noOfElements/r)):
    list_for_nCr.append(noOfElements-i*r)
list_of_nCr_vals=[]
for element in list_for_nCr:
    list_of_nCr_vals.append(big_nCr(element,r))
NoOfArrangements=
np.prod(list_of_nCr_vals)/math.factorial(noOfElements/r)

Try it out for yourself on this Google Colab notebook below

Google Colaboratory

That’s it…(I did say this was going to be a short one…)