# Power Setby Isai Damier, Android Engineer @ Google

```#======================================================================
# 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 )
```