멱집합

멱집합 : 주어진 집합의 모든 부분 집합들로 구성된 집합

 

data = {a,b,c,d} => 원소의 개수 : 2^4 = 16

ex) a,b,c,d,ab,ac....

 

*{a,b,c,d,e,f}의 모든 부분집합을 나열하려면

- a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열하고

- {a,b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.

 

=> {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면

- {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고

- {c,d,e,f}의 모든 부분집합들에 {a,b}를 추가한 집합들을 나열한다.

 

수도코드

- 처음에 p는 공집합, s는 전체 집합

- s가 공집합이 되면 끝난다

- s의 원소들을 하나씩 꺼내서 한번은 원소가 하나 줄어든 집합의 원소들로만 멱집합을 구하고

또 한번은 제외된 원소를 멱집합에 추가한 집합들을 구한다.

 

 

* ex) p집합에 a~f중 포함이 될 수도 있고 안될 수도 있음

- 이런 경우를 위해 include boolean배열을 만들어준다 -> true면 집합에 포함된거고 false면 포함 x

 

자바 코드

- 원래 집합과 boolean집합은 전역변수로 선언하고

- 지금 무슨 원소를 가리키는지를 나타내는 k만 매개변수로 넘겨준다.

- 함수 내에서 처음에는 포함하지 않은 채로 powerSet을 호출하고 다음에 포함한채로 powerSet을 호출한다.

 

이런 방법을 상태공간트리로 생각할 수 있음