Powersets of a list?

[David C. Ullrich]

On Fri, 25 May 2001 23:46:54 +0800, Malcolm Tredinnick
<malcolm at commsecure.com.au> wrote:

>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):

Which I woulda expected to be much slower, but comes out about
ten times faster than his version. It's almost as fast as the 
recursive one I posted, in fact - I suspect the difference there
is I used map() instead of a for loop. (timed with range(15).)

Your trivial case might be a little more trivial - there are problems
here with powerSet([]).

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

David C. Ullrich
***********************
"Sometimes you can have access violations all the
time and the program still works." (Michael Caracena,
comp.lang.pascal.delphi.misc 5/1/01)