[알고리즘] 순열 vs 조합 vs 부분 집합 (순조부)

순열 (Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 nPr

순열을 생성하는 방법

1. 반복문을 통한 순열 생성 : 순열의 갯수가 적을때, 순열의 길이가 변동이 없을때
2. 재귀 호출을 통한 순열 생성 : boolean[ ] 사용
3. 비트마스킹을 통한 순열 생성 : 정수와 비트연산자를 사용
4. 현 순열에서 사전 순으로 다음 순열 생성 ( NextPermutation )
   • 배열을 오름차순으로 정렬한 후 시작
   • 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성
     1. 뒤쪽부터 탐색하며 교환위치 ( i-1 ) 찾기 ( i:꼭대기 )
     2. 뒤쪽부터 탐색하며 교환위치 ( i-1 )와 교환할 큰 값 위치 ( j ) 찾기
     3. 두 위치 값 ( i-1, j ) 교환
     4. 꼭대기위치 ( i ) 부터 맨 뒤까지 오름차순 정렬

기본 코드

import java.util.Arrays;

public class perm {
	static int n = 5, r = 3;
	static int[] numbers;
	static boolean[] isSelected;
	
	public static void main(String[] args) {
		numbers = new int[r];
		isSelected = new boolean[n + 1];
		perm(0);
	}
	
	public static void perm(int cnt) {
		if (cnt == r) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = 1; i <= n; i++) {
			if (isSelected[i]) continue;
			numbers[cnt] = i;
			isSelected[i] = true;
			perm(cnt+1);
			isSelected[i] = false;
		}
	}
}

 

조합(Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합
• 조합의 수식
  • nCr = n! / (n-r)! r!
  • nCr = n-1Cr-1 + n-1Cr, nC0=1

조합을 생성하는 방법

1. 반복문을 통한 조합 생성
2. 재귀 호출을 이용한 조합 생성
3. NextPermutation을 활용
   • 원소 크기와 같은 크기의 int 배열 P를 생성하여 r개 크기 만큼 뒤에서 0이 아닌 값으로 초기화 (ex, 1로 초기화)
   • nextPermutation 알고리즘 한 번 수행시마다 조합이 생성됨
   • P 배열에서 0이 아닌 값을 갖고 있는 위치에 해당하는 원소가 조합에 선택된 것

기본 코드

import java.util.Arrays;

public class comb {
	static int n = 5, r = 3;
	static int[] numbers;
	
	public static void main(String[] args) {
		numbers = new int[r];
		comb(0, 0);
	}
	
	public static void comb(int cnt, int start) {
		if (cnt == r) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		for (int i = start; i <= n; i++) {
			numbers[cnt] = i;
			comb(cnt + 1, i + 1);
		}
	}
}

 

부분 집합(Subset)

• 집합에 포함된 원소들을 선택
• 원소들의 그룹에서 최적의 부분 집합을 찾는 것
• N개의 원소를 포함한 집합
  • 자기 자신과 공집합을 포함한 모든 부분집합(Power set)의 개수는 2^n개
  • 원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가

부분 집합 생성 방법

1. 반복문을 통한 부분집합 생성
2. 재귀 호출을 이용해 생성 : Visited를 이용
3. 바이너리 카운팅을 통한 사전적 순서로 생성

바이너리 카운팅 (Binary Counting)

• 원소 수에 해당하는 N개의 비트열을 이용
• n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미

기본 코드

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