Generate all combinations of integers that sum to 100

partition.py

# Makes use of the "Most Efficient Algorithm" posted here:
#	http://homepages.ed.ac.uk/jkellehe/partitions.php

import csv

def partitions(n):
	a = [0 for i in range(n + 1)]
	k = 1
	y = n - 1
	while k != 0:
		x = a[k - 1] + 1
		k -= 1
		while 2*x <= y:
			a[k] = x
			y -= x
			k += 1
		l = k + 1
		while x <= y:
			a[k] = x
			a[l] = y
			yield a[:k + 2]
			x += 1
			y -= 1
		a[k] = x + y
		y = x + y - 1
		yield a[:k + 1]


f = csv.writer(open("partitions.csv", 'wb'), delimiter=',',quotechar='"', quoting=csv.QUOTE_MINIMAL)
generatedPartitions = partitions(100)
for i in generatedPartitions:
	print i
	f.writerow(i)