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

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()
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  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()
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()
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
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()
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.