Powersets of a list?

[Malcolm Tredinnick]

On Fri, May 25, 2001 at 07:56:52AM -0700, Emile van Sebille wrote:
> This seems to do it:
[... solution snipped...]

Direct from the "more than one way to skin a cat" department, here's
another solution using a different idea (recursion, rather than
enumeration):


def powerSet(seq):
	"""
	To computer the powerset of seq, we need to know the powerset of
	seq[1:] and combine a copy of it with seq[0] (as well as keeping
	an unmodified copy).
	
	We stop the recursion when seq is a singleton -- the powerset of
	[a] is [[a], []].
	"""
	# Trivial case
	if len(seq) == 1:
		return [seq, []]
	# Now do the recursion and combine the results
	subSet = powerSet(seq[1:])
	resultSoFar = subSet[:]
	for set in subSet:
		resultSoFar.append([seq[0]] + set)
	return resultSoFar

# Testing
print powerSet([1])
print powerSet([1, 2])
print powerSet([1, 2, 3])
print len(powerSet(range(10)))

-- 
Eagles may soar, but weasels don't get sucked into jet engines.