Tag Archives: mathematics

Python Partition Calculator

I had been looking to do a little bit more hobby-coding, and I came across this simple math problem which can be solved with a cool recursive Python script.

A partition is a concept in number theory where a positive integer is written as a sum. For example, the only partition of 1 is (1). 2 has (2) and (1+1). 3 has (1+2), (1+1+1), and (3), and so on. Because it’s a sum, order is not important.

The problem of figuring out partitions is not difficult, but it is time-consuming and repetitive once you go beyond calculating all partitions for 4 or 5. Something that makes it a good candidate for automation. It also can be done with some recursion.

The first thing that needs to be done is a recursive call to calculate all the combinations of numbers that would form a partition. I’m going to return a list of lists, where each sublist is a partition. The obvious part to take care of first is the base case:

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])

Next, let’s take a look at when the partition_goal is some number larger than one. The first thing we’d need is to add a list consisting of just that number:

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])

Now we need to loop over all the cases where the lists are more complicated. Let’s take 3, because it’s pretty simple. Once we’ve added the single item list [3] in the step above, we need to add the integer 1 to all lists that add up to 3 – 1, the integer 2 to all lists that add up to 3 – 2 and so on.

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

So for each of the numbers in the i range, we are adding that number to every list we can create recursively (j) where that list sums to partition_goal – i. Lastly, we need to call our recursive method, and then remove all the sublists which are identical when unordered ([1,1,2] and [1,2,1] are just one partition of 4). We do this using the Counter module.

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

list_of_lists = recursive_partition(n)

counted = Counter(tuple(sorted(entry)) for entry in list_of_lists)

print(list(counted.keys()))

The variable counted actually gets a dictionary Python object, so I turned it into a list in the print statement. The keys of a Counter are tuples, so the end result is a list of tuples where every tuple is a partition. Lastly let’s make some interface changes so we can take command line arguments or ask the user for input.

from collections import Counter
import sys

n = 1
# partition goal
if len(sys.argv) > 1:
    n = sys.argv[1]
else:
    n = int(input("What number do you want the partitions for?"))

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

list_of_lists = recursive_partition(n)

counted = Counter(tuple(sorted(entry)) for entry in list_of_lists)

print(list(counted.keys()))

And remember this is Python 3 notation. You can find this little project on Github here.