Unit 2. powerset

 powerset이란?  특정 집합의 공집합을 포함한 모든 부분 집합을 멱집합(powerset)이라 한다.

 

def powerset(level):
    length = len(List)
    if level == length:
        element = []
        for i in range(0, length):
            if include[i]:
                element.append(List[i])
        print element
        return
    else:
        include[level] = False
        powerset(level+1)
        include[level] = True
        powerset(level+1)
 
List = ['a','b','c']
include = [False for _ in xrange(len(List))]
powerset(0)

[]

['c']

['b']

['b', 'c']

['a']

['a', 'c']

['a', 'b']

['a', 'b', 'c']

 List의 level은 0번부터 len(list)까지의 인덱스를 나타낸다.  level에서 list[level]를 포함하는지 하지 않는지에 따라서 분기가 갈린다.  가장 마지막 레벨에서 요소들을 모두 포함하지 않는 공집합부터 하나, 둘 그리고 모두를 포함하는 요소들까지 갈린 분기들의 마지막이 되어 출력된다.

powerset.py