순열, 조합, 부분집합, 멱집합 정리

완전 탐색은 모든 경우의 수를 따져 찾는 경우를 말한다.

자주 사용 되는 이론을 정리 해두려고 한다.

 

• 순열 : n개의 원소 중 r개의 원소를 순서가 유효하게 꺼내는 경우의 수( 중복을 허용함)
• 조합 : n개의 원소 중 r개의 원소를 순서가 유효하지 않게 꺼내는 경우의 수(중복을 허용하지 않음)
• 부분 집합 : 하나의 집합을 이루는 원소들
• 멱집합 : 공집합을 포함한 모든 집합

 

 

순열

---

집합 A = {a, b, c, d} 일 때 이중 2개의 원소를 뽑는 경우의 수는

{ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc}가 된다.

 

방식은 재귀적인 방식을 통해 구현하였다.

 

ab, ac 가 선택되는 과정을 보여주면

result =  [a, b]

arr = [ c,  d]

이 상태에서 

arr.add(i, result.remove(result.size() - 1));

위 의 코드를 통해

result = [a]

arr = [b, c, d]

로 다시 돌려놓는다

 

다시 반복문을 통해

result = [a, c]

arr = [b, d] 

가 된다.

이 방식을 계속 해서 반복문을 통해 재귀적으로 돌리면 모든 순열 경우의 수를 확인 할 수 있다.

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	
	static StringBuilder sb = new StringBuilder();
		
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		List<String> arr = new ArrayList<String>();
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		for(int i = 0 ; i < 4 ; i++) {
			arr.add(st.nextToken());
		}
		
		List<String> result = new ArrayList<String>();
		reculsion(arr, result, arr.size(), 2);
		
	}
	
	public static void reculsion(List<String> arr, List<String> result, int size, int r) {
		if(r == 0) {
			System.out.println(result.toString());
			return;
		}
		
		for(int i = 0 ; i < size ; i++) {
			
			result.add(arr.remove(i));
			reculsion(arr, result, size - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}
	}
}

결과는 이렇게 나오게 된다.

 

 

 

 

조합

---

집합 A = {1, 2, 3, 4} 일 때 이중 2가지 조합을 고르는 경우의 수는

{{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}} 이렇게 된다.

조합은 중복을 허용하지 않기 때문에 {1, 2}와 {2, 1} 은 같은 경우의 수로 친다.

 

순열과 방식은 비슷하지만 다른점은 인덱스의 추가다.

현재 있는 위치의 다음 위치만 조합이 될 수 있기 때문에 인덱스 인자를 추가했다.

 

방식을 {1, 2}, {1, 3} 이 선택되는 과정을 통해 보여주면,

arr = {1, 2, 3, 4}

result = {1, 2} 이상태일 때 index = 1, r = 1 이다.

이상태의 result 리스트를 프린트 한 뒤,

재귀가 끝난다.

result.remove(result.size() - 1);

이 코드를 통해 

arr = {1, 2, 3, 4}

result = {1} 상태고 index = 0, r = 2 이 된다.

 

뒤에 다시 반복문을 통해

arr = { 1, 2, 3, 4}

result = { 1, 3 } 상태고 index = 2, r = 1 이 된다.

이 된다.

이런 재귀적인 방식을 통해 조합을 표현한다.

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	
	static StringBuilder sb = new StringBuilder();
		
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		List<String> arr = new ArrayList<String>();
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		for(int i = 0 ; i < 4 ; i++) {
			arr.add(st.nextToken());
		}
		
		List<String> result = new ArrayList<String>();
		reculsion(arr, result, arr.size(), 2, 0);
		
	}
	
	public static void reculsion(List<String> arr, List<String> result, int size, int r, int index) {
		if(r == 0) {
			System.out.println(result.toString());
			return;
		}
		
		for(int i = index ; i < size ; i++) {
			
			result.add(arr.get(i));
			reculsion(arr, result, size, r - 1, i + 1);
			result.remove(result.size() - 1);
		}
	}
}

결과는 이렇게 나오게 된다.

 

 

 

 

 

 

부분집합, 멱집합

---

 

모든 부분 집합이 멱집합이기 때문에 한번에 설명하겠다.

 

집합 A = {a, b, c, d} 의 부분집합은 

{ {}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}} 

이렇게 나오게 된다.

 

 

로직의 순서를 말하면

 

a 가 있고 없고 {a, b, c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a}, {b}, {c}, {d}, {}

b 가 있고 없고 {b, c, d}, {b, c}, {b, d}, {c, d}, {b}, {c}, {d}, {}

c 가 있고 없고 {c, d} , {c}, {d}, {}

d 가 있고 없고 {d}, {}

 

위 와 같은 방식으로 확장 되는 방식이다.

 

부분 코드를 통해 설명을 하자면

state[index] = false;
reculsion(arr, state, index + 1, end);
	
state[index] = true;
reculsion(arr, state, index + 1, end);

state[index] 를 ture, false 값으로 번갈아 넣어주는것은

위에서 설명한 이유와 같이 해당 문자를 포함하는가 포함하지 않는가를 나누어서 판단해주어야 하기 때문이다.

 

재귀적인 코드를 통해 모든 부분집합을 구하는 멱집합을 구할 수 있다.

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	
	static StringBuilder sb = new StringBuilder();
		
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		String[] arr = new String[4];
		boolean[] state = new boolean[4];
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		for(int i = 0 ; i < 4 ; i++) {
			arr[i] = st.nextToken();
		}
		
		reculsion(arr, state, 0, arr.length);
		
	}
	
	public static void reculsion(String[] arr, boolean[] state, int index, int end) {
		if(index >= end) {
			for(int i = 0 ; i < end ; i++) {
				
				if(state[i]) {
					System.out.print(arr[i]+ " ");
				}
			}
			
			System.out.println();
			return;
		}
		
		state[index] = false;
		reculsion(arr, state, index + 1, end);
		
		state[index] = true;
		reculsion(arr, state, index + 1, end);
		
	}
}

위 코드에서는 4개를 한정적으로 했지만 배열의 크기 조정을 통해 더많은 값을 할 수 있다.

결과는 아래와 같이 나온다.