[알고리즘] 멱집합 powerset

인프런 무료 강의 권오흠교수님 '영리한 프로그래밍을 위한 알고리즘 강좌' 보면서 공부한 내용입니다.
부족한 내용이나 잘못된 내용은 댓글남겨주시면 감사하겠습니다!

출처 : https://inf.run/iezc

멱집합 : 어떤 집합의 모든 부분 집합의 집합

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

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

// {c, d, e, f} : 집합 s = k 번째부터 마지막 원소까지 연속된 원소들
// {a, b} : 집합 P = 처음부터 k-1 번째 원소들 중 일부

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

 

/*
 * 멱집합 powerset : 7-01 
 */
package edu.recursion;

public class Powerset07_01 {
	
	/*
	 문제) S의 멱집합을 출력
	 poserSet(s)
	 if s is an empty set
	 	print nothing;
	 else
	 	let t be the first element of s;
	 	find all subsets of s-{t} by calling powerSet(S-{t});
	 	print the subsets;
	 	print the subsets with adding t;
	 	
	 // 이렇게 하기 위해선 powerSet 함수는 여러 개의 집합들을 return해야함
	 
	 문제) S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력
	 powerSet(P, S)
	 if s is an empty set
	 	print P;
	 else
	 	let t be the first element of s;
	 	powerSet(P. s-{t});
	 	powerSet(PU. s-{t});
	 // recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야한다는 의미.
	 // 두 번쨰 집합의 모든 부분 집합들에 첫 번째 집합을 합집합하여 출력	
	 
	 	
	 
	 */
}

 

/*
 * 멱집합 powerset : 7-02
 * 
 * 멱집합 : 어떤 집합의 모든 부분 집합의 집합
 * ->
 * f 
 * e 
 * e f 
 * d 
 * d f 
 * d e 
 * d e f 
 * 
 */
package edu.recursion;

public class Powerset07_02 {

	public static void main(String[] args) {
		powerSet(3);
	}
	
	// 문제) data[k], ..., data[n-1]의 멱집합을 구한 후 각각에 include[i] = true, i=0, ..., k-1인 원소를 추가하여 출력
	private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
	private static int n=data.length;
	private static boolean[] include = new boolean[n];
	
	public static void powerSet(int k){
		if(k==n){
			for (int i=0; i<n; i++)
				if (include[i]) System.out.print(data[i] + " ");
			System.out.println();
			return;
		}
		// data[k] 포함하지 않는 경우
		include[k] = false;
		powerSet(k+1);
		
		// data[k] 포함하는 경우
		include[k] = true;
		powerSet(k+1);
		
		// 처음 이 함수를 호출할 떄는 powerSet(0)로 호출.
		// 즉, P는 공집합이고, S는 전체집합
	}
}

 

 상대공간트리 state space tree
 - 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리
 - 트리의 모든 노드들을 방문하면 해를 찾을 수 있음
 - 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술

/*
 * 멱집합 powerset : 7-03 
 */
package edu.recursion;

public class Powerset07_03 {
	
	public static void main(String[] args) {
		powerSet(3);
	}
	
	private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
	private static int n=data.length;
	private static boolean[] include = new boolean[n]; // include : 트리상에서 현재 나의 위치를 표현
	
	public static void powerSet(int k){ // k : 트리상에서 현재 나의 위치를 표현
		if(k==n){ // n : 만약 내 위치가 리프노드일 경우
			for (int i=0; i<n; i++)
				if (include[i]) System.out.print(data[i] + " ");
			System.out.println();
			return;
		}
		// data[k] 포함하지 않는 경우
		include[k] = false;
		powerSet(k+1); // 먼저 왼쪽으로 내려갔다가
		
		// data[k] 포함하는 경우
		include[k] = true;
		powerSet(k+1); // 이번엔 오른쪽으로 내려감
	}
}