A의 모든 부분집합을 원소로 하는 집합을 A의 멱집합(power set)이라 하고 P(A) 또는 2A로 나타낸다.
예를들어 S = { 1 , 2, 3, 4 } 일때 부분집합(power set) = {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}} 이다.
따라서 임의의 유한집합에 대해서 그 크기가 |A| = n 이라고 할때, 부분집합의 개수는 2n 개가 된다.
그럼 컴퓨터에서 임의의 집합의 모든 부분집합을 출력하는 알고리즘은 어떻게 될까?
사실 생각해보면 { a, b, c, d, e, f } 의 모든 부분집합을 나열하려면 a 를 제외한 { b, c, d, e, f } 의 모든 부분집합들을 나열하고
{ b, c, d, e, f }의 모든부분집합에 { a } 를 추가한 집합들을 나열하면 되는 것돠 동일하다.
또한 { b, c, d, e, f}의 모든 부분집합에 { a } 를 추가한 집합들을 나열하려면 { b } 제외한
{ c d, e, f } 의 모든 부분집합들에 { a } 를 추가한 집합들을 나열하고
{ c d, e, f } 의 모든 부분집합에 { a, b } 를 추가한 집합들을 나열하면 된다.
이 설명이 내포하고 있는 것은 재귀(recursion)이다.
즉, S의 멱집합을 출력하라는 문제는 재귀로 풀수 있다.
물론 재귀 말고도 멱집합을 구하는 알고리즘은 더 있는데 여기서는 그 모든 방법을 다 알아보도록 한다.
재귀함수는 반드시 빠져나갈 베이스케이스가 있어야 한다고 하였는데 여기서 베이스 케이스는 S가 비어 있는 경우 ( Φ (공집합) )이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static ArrayList < String > getpowerset(int a[], int n, ArrayList < String > ps) {
if (n < 0) {
return null;
}
if (n == 0) {
if (ps == null) ps = new ArrayList < String > ();
ps.add(" ");
return ps;
}
ps = getpowerset(a, n - 1, ps);
ArrayList < String > tmp = new ArrayList < String > ();
for (String s: ps) {
if (s.equals(" ")) tmp.add("" + a[n - 1]);
else tmp.add(s + a[n - 1]);
}
return ps;
}
Colored by Color Scripter
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static <T> List<List<T>> powerset(Collection<T> list) {
List<List<T>> ps = new ArrayList<List<T>>();
ps.add(new ArrayList<T>()); // add the empty set
// for every item in the original list
for (T item : list) {
List<List<T>> newPs = new ArrayList<List<T>>();
for (List<T> subset : ps) {
// copy all of the current powerset's subsets
newPs.add(subset);
// plus the subsets appended with the current item
List<T> newSubset = new ArrayList<T>(subset);
newSubset.add(item);
newPs.add(newSubset);
}
// powerset is now powerset of list.subList(0, list.indexOf(item)+1)
ps = newPs;
}
return ps;
}
Colored by Color Scripter
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static < T extends Comparable < ?super T >> LinkedList < LinkedList < T >> BinPowSet(
LinkedList < T > A) {
LinkedList < LinkedList < T >> ans = new LinkedList < LinkedList < T >> ();
for (int i = 0; i < ansSize; ++i) {
String bin = Integer.toBinaryString(i); //convert to binary
while (bin.length() < A.size()) bin = "0" + bin; //pad with 0's
LinkedList < T > thisComb = new LinkedList < T > (); //place to put one combination
for (int j = 0; j < A.size(); ++j) {
if (bin.charAt(j) == '1') thisComb.add(A.get(j));
}
Collections.sort(thisComb); //sort it for easy checking
ans.add(thisComb); //put this set in the answer list
}
return ans;
}
Colored by Color Scripter
|
레퍼런스
'알고리즘(Algorithm) > 수학(Math)' 카테고리의 다른 글
호너의 법칙(Horner's method) (0) | 2019.07.19 |
---|---|
순열(permutation) 알고리즘 (0) | 2019.07.10 |