멱집합 알고리즘

공부한 사이트

https://www.youtube.com/watch?v=nkeMRRIVW9s&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=7

멱집합

집합S에 대한 모든 부분집합

 

부분집합의 개수는 각각 원소에 대해 포함o, x  총 2가지 케이스를 가질 수 있다. 

따라서 2^n가지 (n=원소의 개수)

 

재귀적인 관점으로 보면

S={ a, b, c }의 멱집합은

    1. a를 제외한 b,c의 부분집합

    2. b, c의 부분집합에 a를 더한 경우

 (1) + (2)으로 이루어져 있다.

 

 

 

Ver.1

부분집합을 저장하지 않고 단순히 출력하는 경우

모든 경우의 수를 나타내는 상태공간트리의 마지막 노드를 출력한다고 생각한다.

 

마지막 노드는 모든 원소들이 포함될지 안될지 결정이 완료된 상태로 

집합S의 원소x에 대해 포함될 경우( include[k] = true) 그렇지 않을 경우( include[k] = false)으로

상태를 다르게 주어 재귀한다.

기저케이스는 k == n일경우 ( 모든 원소가 결정을 마친 상태 )

 

 

강의에서는 

 

package repeat;

public class Powerset {
	private static char data[] = {'a', 'b','c','d','e','f'};
	private static int n = data.length;
	private static boolean[] include = new boolean[n];
	
	// 트리에서 마지막 값이 구하는 해
	// 트리상에서 현재 나의 위치: k(=level)단계, true값을 가진 원소노드와 일치하는 위치에 있음
	public static void powerSet(int k) { //부분집합을 구할 범위는 k를 이용해 표현
		
		if(k == n) {//base case: 부분집합을 구할 범위가 없을 경우 p를 출력, 
					// 즉 마지막 노드일경우 모든 요소들의 포함여부가 결정됨 따라서 그냥 출력함.
			for(int i=0; i<n; i++) 
				if(include[i]) System.out.print(data[i] + " ");
			System.out.println();
			return;
		}
		include[k]=false; //포함하지 않는 경우
		powerSet(k+1);
		include[k]=true; //k를 포함하는 경우	
		powerSet(k+1); 
	}
	public static void main(String[] args) {
		powerSet(0);
	}

}

 

 

Ver.2

메모리에 부분집합을 저장할 경우 사용할 수 있는 알고리즘으로 

- idx는 첫번째 요소를 의미한다.

- 반환값(1)을 전역변수에 저장해 공유한다.

- 기저 케이스는 부분집합을 구할 범위(1)가 원소 하나일 경우 

  포함O, X 를 list에 저장한다.

-  (2)를 구하기 위해 list에 list.get(idx)요소를 list의 모든 요소에 추가한다.

 

단점은 메모리가 부분집합의 개수만큼 필요하다.

 

package repeat;
import java.util.*;

public class PowerSet_2 {
	public ArrayList<String> list = new ArrayList<String>();
	String s[] = new String[]{"a", "b", "c"};
    
	public void power(int idx) {
		if(idx == s.length-1) {
			list.add(s[idx]);
            list.add(" ");
			return;
		}
        else {
			power(s, idx+1); //s[idx]를 포함하지 않는 경우
			
			//s[idx]요소를 포함시키는 경우
			int n=list.size();
			
			for(int i=0; i<n;i++) {
				list.add(s[idx]+list.get(i));
			}

			return;
		}
	}
	public static void main(String[] args) {
		PowerSet_2 ps= new PowerSet_2();
		ps.power(0);
		Collections.sort(ps.list);
	}
}