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.
Michael Elgart 