#======================================================================
# Author: Isai Damier
# Title: Power Set
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Given a set of objects (e.g. characters), find the power set.
#
# Sample Input: [a,b,c]
# Sample Output: [[a,b,c],[a,b],[a,c],[a],[b,c],[b],[c],[]]
#
# Technical Details:
# This solution is one of the most powerful and most elegant results
# of bitwise operations. To find the powerset of any set of size n,
# simply start with an ALL_BITS number of size n and count down:
# [a,b,c],[a,b ], [a, c],[a ],[ b,c],[ b ],[ c],[ ]
# 1 1 1 , 1 1 0 , 1 0 1 , 1 0 0 , 0 1 1 , 0 1 0 , 0 0 1 , 0 0 0.
#
# This solution is important, for example, because all problems whose
# solutions depend on finding the combination C(n,k) of a set can be
# solved by finding the power set of said set. The power set,
# of course, is the general solution, and thus is an inefficient
# approach for solving particular instances.
#======================================================================
def powerSet( aList ):
# return None if set is None or empty
if ( aList is None or len( aList.strip() ) == 0 ):
return None
powset = []
length = len( aList )
bits = "1"*length
# extract power set by counting down in 'binary'
b = int( bits, 2 )
while ( b >= 0 ) :
# get bit representation of new subset
bits = bin( b )
bits = bits[2:]
subset = "" # empty subset holder
# Python drops leading 0s so that if 7==111, then 3 != 011 but 3==11
k = length - len( bits )
for c in bits: # assemble subset from bits
if '1' == c:
subset += aList[k]
k += 1
b -= 1
powset.append( subset ) # add subset to power set
return powset
import unittest
from algorithms import bitwise as bits
class Test( unittest.TestCase ):
def testPowerSet( self ):
expected = ["abc", "ab", "ac", "a", "bc", "b", "c", ""]
result = bits.powerSet( "abc" );
self.assertEquals( expected, result )
