순열, 조합, 부분집합

1. 순열

서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

nPr
nPr = n * (n-1) * (n-2) * ... * (n-r+1)

nPn = n!
n! = n * (n-1) * (n-2) * ... * 2 * 1

 

다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련

N개의 요소들에 대해서 n! 개의 순열들이 존재한다.

n>12 인 경우, 시간 복잡도 폭발적으로 증가

반복문을 통한 순열 생성

for i from 1 to 3
	for j from 1 to 3
		if j != i then
			for k from 1 to 3
				if k != i and k != j then
					print i, j ,k
				end if
			end for
		end if
	end for
end for

public class Permutation {
	public static void main(String[] args) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (i != j) {
					for (int k = 0; k < 3; k++) {
						if (k != i && k != j) {
							System.out.println(i + " " + j + " " + k);
						}
					}
				}
			}
		}
	}
}

/*
 * 0 1 2
 * 0 2 1
 * 1 0 2
 * 1 2 0
 * 2 0 1
 * 2 1 0
*/

재귀 호출을 통한 순열 생성

numbers[] // 순열 저장 배열
isSelected[] // 인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열
perm(cnt) // cnt : 현재까지 뽑은 순열 수의 개수
	if cnt == N
		순열 생성 완료
	else 
		for i from 1 to 3
			if isSelected[i] == true then continue
			numbers[cnt] = i
			isSelected[i] = true
			perm(cnt+1)
			isSelected[i] = false
		end for

public class Permutation2 {
	static int[] numbers = { 1, 2, 3, 4, 5 };
	static boolean[] isSelected;
	static int[] res;

	public static void main(String[] args) {
		isSelected = new boolean[numbers.length];
		res = new int[numbers.length];
		perm(0);
	}

	static void perm(int cnt) {
		if (cnt == numbers.length) {
			System.out.println(Arrays.toString(res));
		}
		for (int i = 0; i < numbers.length; i++) {
			if(isSelected[i] == true) continue;
			isSelected[i] = true;
			res[cnt] = numbers[i];
			perm(cnt+1);
			isSelected[i] = false;
		}
	}
}

비트마스킹을 통한 순열 생성

// nPn -> N개의 원소로 만들 수 있는 모든 순열 생성

input[] // 숫자 배열
numbers[] // 순열 저장 배열

perm(cnt, flag) // cnt: 현재까지 뽑은 순열 원소의 개수, flag: 선택된 원소에 대한 비트 정보를 표현하는 정수
	if (cnt == N)
			// 순열 생성 완료
	else
		for i from 0 to N-1
			if(flag & i << i) != 0 then continue
				numbers[cnt] = input[i]
				perm(cnt+1, flag | 1<<i)
		end for
end perm()

현 순열에서 사전 순으로 다음 순열 생성 - NextPermutaion

알고리즘

배열을 오름차순으로 정렬한 후 시작한다.

아래 과정을 반복하여 사전 순으로 다음 큰 순열 생성(가장 큰 내림차순 순열을 만들 때까지 반복한다.

1. 뒤쪽부터 탐색하여 교환위치 (i - 1) 찾기 i : 꼭대기
2. 뒤쪽부터 탐색하여 교환위치 (i - 1)와 교환할 큰 값 위치(j) 찾기
3. 두 위치 값 (i - 1, j) 교환
4. 꼭대기위치(i)부터 맨 뒤까지 오름차순 정렬

2. 조합

서로 다른 n개의 원소 중 r개를 순서 없이 골래낸 것

nCr = n! / ((n-r)! * r!) , (n >= r)

nCr = n-1Cr-1 + n-1Cr ==> 재귀적 표현
nC0 = 1

반복문을 통한 조합 생성

for i from 1 to 4
	for j from i+1 to 4
		for k from j+1 to 4
			print i, j , k
		end for
	end for
end for

public class Combination1 {
	public static void main(String[] args) {
		for (int i = 1; i < 5; i++) {
			for (int j = i + 1; j < 5; j++) {
				for (int k = j + 1; k < 5; k++) {
					System.out.println(i + " " + j + " " + k);
				}
			}
		}
	}
}

재귀 호출을 이용한 조합 생성 알고리즘

nCr // n개의 원소 중 r개 원소를 갖는 조합 생성
input[] // n 개의 원소를 가지고 있는 배열
numbers[] // r개의 크기의 배열, 조합이 저장될 배열

comb(cnt, start) // cnt: 현재까지 뽑은 조합 원소 개수, start: 조합 시도할 원소의 시작 인덱스
	if cnt == r
		조합 생성 완료
	else
		for i from start to n-1
			numbers[cnt] = input[i]
			comb(cnt+1, i+1)
		end for
end comb()

public class Combination2 {
	static int [] numbers = {1,2,3,4,5};
	static int [] res;
	static int R = 3;
	static int N = numbers.length;
	public static void main(String[] args) {
		res = new int[R];
		combi(0,0);
	}
	
	static void combi(int cnt, int idx) {
		if (cnt == R) {
			System.out.println(Arrays.toString(res));
			return;
		}
		for(int i = idx ; i < N; i++) {
			res[cnt] = numbers[i];
			combi(cnt+1,i+1);
		}
		
	}
}

3. 부분집합

집합에 포함된 원소들을 선택하는 것

다수의 중요 알고리즘들이 원소들의 그룹에서 최적을 부분 집합을 찾는 것

부분집합의 수
 - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다.
 - 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.

반복문을 통한 부분집합 생성

FOR i in 1 -> 0
	selected[1] = i
	FOR j in 1 -> 0
		selected[2] = j
		FOR k in 1 -> 0
			selected[3] = k
			// 생성된 부분집합 출력
			FOR m in 1 -> 3
				if selected[i] == 1 then
					print i

public class PowerSet1 {
	public static void main(String[] args) {
		int [] numbers = {1,2,3};
		boolean [] selected = new boolean[numbers.length];
		
		for (int i = 1 ; i >= 0 ; i--) {
			selected[0] = !selected[0];
			for(int j = 1; j>=0;j--) {
				selected[1] = !selected[1];
				for(int k = 1; k>=0;k--) {
					selected[2] = !selected[2];
					for(int m = 0 ; m <3 ;m++) {
						if (selected[m]) {
							System.out.print(numbers[m]+" ");
						}
					}
					System.out.println();
				}
			}
		}
	}
}

재귀적 구현을 통한 생성

input[] // 숫자 배열
isSelected[] // 부분집합에 포함/ 비포함 여부를 저장한 배열

generateSubSet(cnt)
		if (cnt == N)
			부분집합 완성
		else
			isSelected[cnt] = true
			generateSubSet(cnt + 1)
			isSelected[cnt] =  false
			generateSubSet(cnt + 1)
end generateSubSet

public class PowerSet2 {
	static int [] numbers = {1,2,3,4};
	static int [] res;
	static boolean [] isSelected;
	static int N = numbers.length;
	public static void main(String[] args) {
		res = new int[N];
		isSelected = new boolean[N];
		
		powerSet(0);
	}
	static void powerSet(int cnt) {
		if(cnt == N) {
			for(int i = 0 ; i < N ; i++) {
				if(isSelected[i]) {
					System.out.print(numbers[i]+" ");
				}
			}
			System.out.println();
			return;
		}
		isSelected[cnt] = true;
		powerSet(cnt+1);
		isSelected[cnt] = false;
		powerSet(cnt+1);
	}
}

부분 집합의 합 문제

유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 워소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제

ex) {-7, -3, -2, 5, 8}, {-3, -2, 5}는 앞 집합의 부분집합이면서 합이 0이므로 참이 된다.