A sequence-like object that represents all the partitions of a set, allowing iteration and random access of the partitions and using very little memory

partition-set.py

from collections import defaultdict



'''
Represents the sequence of all partitions of a set, by increasing number of 
partition. This is a pseudo-sequence, each item of the sequence is generated
rather than stored.
'''
class partition_set(object):
	def __init__(self, item_list,
	             min_partition_size = 1,
	             max_partition_size = None):
		self.item_list = tuple(item_list)

		self.min_partition_size = min_partition_size
		if max_partition_size is None:
			self.max_partition_size = len(self.item_list)
		else:
			self.max_partition_size = max_partition_size

		self._build_partition_len_table(len(self.item_list))
		self.len = sum(self.partition_len[len(self.item_list), k] for k in range(self.min_partition_size, self.max_partition_size + 1))

	def __len__(self):
		return self.len

	def __getitem__(self, i):
		if i >= len(self):
			raise IndexError

		n = len(self.item_list)
		for k in range(self.min_partition_size, self.max_partition_size  + 1):
			partition_len = self.partition_len[n, k]
			if i < partition_len:
				return self._get_item_from_partition(n, k, i)
			i -= partition_len

	def _get_item_from_partition(self, n, k, i):
		# Partition into a single element
		if k == 1:
			return [[item for item in self.item_list[:n]]]
		# Partition into n elements
		elif k == n:
			return [[item] for item in self.item_list[:n]]
 		# Non-trivial case
		else:
			a = k * self.partition_len[n - 1, k]
			if i < a:
				partition = self._get_item_from_partition(n - 1, k, i / k)
				partition[i % k].append(self.item_list[n-1])
			else:
				i -= a
				partition = self._get_item_from_partition(n - 1, k - 1, i)
				partition.append([self.item_list[n - 1]])
			return partition

	def _build_partition_len_table(self, item_count):
   		# Computes the number of partitions of size 1, 2, 3, ... with Stirling numbers of the second kind
		self.partition_len = defaultdict(lambda:1)
		for n in range(3, item_count + 1):
			for k in range(2, n):
				self.partition_len[n, k] = k * self.partition_len[n - 1, k] + self.partition_len[n - 1, k - 1]


'''
Usage example
'''

S = 'ABCDE'
S_partitions = partition_set(S)

# Get the number of partitions
print len(S_partitions), 'elements'

# Get the 42th element of the partition set
print 'element 42 is ', S_partitions[42]

# Print all the element of the partition set
for item_list in S_partitions:
	print ', '.join(''.join(item) for item in item_list)