Power Set
by Isai Damier

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