[알고리즘] 순열, 조합, 부분집합 Java

public class 순조부연습 {

	static int N, M;
	//순열
	static boolean[] isSelected; 
	//static int[] tgt; 
	
	//비트마스킹(순열), 조합
	static int[] tgt, src;
	static int[][] dp; // 조합- dp
	
	//부분집합
	//static boolean[] isSelected;
	
	public static void main(String[] args) {
		
		//1. 순열 기본
		perm1(0);
		//2. 중복 순열
		perm2(0);
		//3. 비트마스킹 순열
		perm_bit(0, 0);
		//4. np 활용 순열
		np();
		
		//1. 조합 기본
		comb1(0, 0);
		//2. 조합 기분2
		comb3(0, 0);
		//3. 중복 조합
		comb2(0, 0);
		//4. DFS
		dfs(0, 0);
		//5. 조합+dp
		comb_dp();
		
		//1. 부분집합
		subset(0);
		//2. 비트마스킹 부분집합
		subset_bit();
	}

	//순열------------------------
	//1. 순열 기본
	static void perm1(int cnt) {
		if (cnt == M) {
			//순열 생성
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (isSelected[i]) continue;
			isSelected[i] = true;
			tgt[cnt] = i;
			perm1(cnt + 1);
			isSelected[i] = false;
		}
	}
	//2. 중복 순열
	static void perm2(int cnt) {
		if (cnt == M) {
			//순열 생성
			return;
		}
		for (int i = 0; i < N; i++) {
			tgt[cnt] = i;
			perm2(cnt + 1);
		}
	}
	//3. 비트마스킹 순열
	static void perm_bit(int cnt, int flag) {
		if (cnt == M) {
			//순열 생성
			return;
		}
		for (int i = 0; i < N; i++) { ///////////////////////틀림
			if ((flag & 1<<i) != 0) continue;
			tgt[cnt] = i;
			perm_bit(cnt + 1, (flag|1<<i)); ///////////////////////틀림
		}
	}
	//4. np 활용 순열
	static boolean np() {
		int[] dest = src;
		
		int top = dest.length - 1;
		while (top > 0 && dest[top - 1] >= dest[top]) top--; //꼭대기 찾기
		
		if (top == 0) return false;
		
		int pre = dest.length - 1;
		while (dest[top - 1] >= dest[pre]) pre--; //꼭대기 뒤에서 꼭대기 앞점보다 큰 요소 찾음
		
		swap(dest, top-1, pre); //그 두 점 swap
		
		int sw = dest.length - 1;
		while (top < sw) swap(dest, top++, sw--);
		
		return true;
	}
	static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp; ///////////////////////틀림
	}
	//순열 끝-------------------------------------
	
	//조합--------------------------------
	//1. 조합 기본
	static void comb1(int cnt, int start) {
		if (cnt == M) {
			//조합 생성
			return;
		}
		for (int i = start; i < N; i++) {
			tgt[cnt] = i;
			comb1(cnt+1, i+1);
		}
	}
	//3. 중복 조합
	static void comb2(int cnt, int start) {
		if (cnt == M) {
			//조합 생성
			return;
		}
		for (int i = start; i < N; i++) {
			tgt[cnt] = i;
			comb2(cnt + 1, i); // 중복순열 - 자기 자신부터 선택 가능
		}
	}
	//2. 조합 기분2
	static void comb3(int tgtIdx, int srcIdx) {
		if (tgtIdx == tgt.length) {
			return;
		}
		if (srcIdx == src.length) {
			return;
		}
		
		tgt[tgtIdx] = srcIdx;
		
		comb3(tgtIdx + 1, srcIdx + 1); // 선택 했을 경우
		comb3(tgtIdx, srcIdx + 1); //선택 안했을 경우
	}
	//4. DFS
	static void dfs(int cnt, int point) {
		if (cnt == N) {
			return;
		}
		
		dfs(cnt + 1, point);
		dfs(cnt + 1, point + src[cnt]);
	}
	//5. 조합+dp
	static void comb_dp() {
		for (int i = 1; i <= N; i++) { //n
			for (int j= 0; j <= i; j++) { //r
				if (i == 0 || i == N) dp[i][j] = 1;
				else {
					dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
				}
			}
		}
	}
	//조합 끝-------------
	//부분집합-------------
	//1. 부분집합
	static void subset(int cnt) {
		if (cnt == N) {
			//부분집합 생성
			return;
		}
		isSelected[cnt] = true;
		subset(cnt + 1);
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
	//2. 비트마스킹 부분집합
	static void subset_bit() {
		int count = 1<<N;
		for (int i = 0; i < count; i++) {
			for (int j = 0; j < N; j++) {
				if ((i & 1<<j) != 0) {
					//할 일. 순열은 미방문일 때 아래 코드 가능했음 부분집합은 방문일 때 가능
				}
			}
		}
	}
	//부분집합 끝-------------
}