순열

순열이란 서로 다른 N개의 원소중에 R개를 뽑아 줄 세우는 경우의 수이다 (중복 X)
N개에서 R개를 뽑을 때 순서를 고려하여 가능한 모든 경우의 수를 포함한다

순열 Java 코드

public class PermutationDupX {
	static int[] Original = { 100, 200, 300, 400, 500, 600 };
	static int[] result;
	static boolean[] visited;
	static int N = Original.length;
	static int cnt = 0;

	// 6개중에 3개를 뽑는 순열의 수 (중복 x) 6P3 = 6x5x4 = 120
	public static void main(String[] args) {

		visited = new boolean[N];
		result = new int[3];
		permutation(0);
		System.out.println(cnt);

	}

	public static void permutation(int depth) {
		if (depth == 3) {
			for (int num : result) {
				System.out.print(num + " ");
			}
			System.out.println();
			cnt++;
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[depth] = Original[i];
				permutation(depth + 1);
				visited[i] = false;
			}
		}
	}
}

중복순열

중복순열이란 서로 다른 N개의 원소중에 R개를 뽑아 줄 세우는 경우의 수이며, 이때 한 번 사용한 원소를 다시 사용할 수 있다. 즉 1 2 3 4에서 3개를 뽑아 줄 세울 때 1 1 1, 1 2 2 와 같은 경우가 가능하다

중복순열 Java 코드

public class PermutationDupO {
	static int [] Original = {100,200,300,400,500,600};
	static int[] result;
	static int N = Original.length;
	static int cnt = 0;
	//6개중에 3개를 뽑는 순열의 수 (중복 o) 6Pi3 = 6x6x6 = 216
	public static void main(String[] args) {
		
		result = new int[3];
		permutation(0);
		System.out.println(cnt);

	}
	
	public static void permutation(int depth) {
		
		if(depth == 3) {
			for(int num : result) {
				System.out.print(num+" ");
			}System.out.println();
			cnt++;
			return;
		}
		
		for(int i = 0; i < N; i++) {
			result[depth] = Original[i];
			permutation(depth+1);
		}
	}
}

조합

조합이란 서로 다른 N개의 원소중에 R개를 뽑는 경우의 수이다 (중복 X)
N개에서 R개를 뽑을 때 순서를 고려하지 않고 단순히 뽑는 모든 경우의 수를 포함한다
1 2 3 4 와 4 3 2 1 은 같은 경우의 수로 취급한다

조합 Java 코드

public class CombinationDupX {

	static int[] Original = { 100, 200, 300, 400, 500, 600 };
	static int[] result;
	static int N = Original.length;
	static int cnt = 0;

	// 6개중에 3개를 뽑는 조합의 수 (중복x) 6C3 = 6x5x4/3x2x1 = 20
	public static void main(String[] args) {

		result = new int[3];
		combination(0, 0);
		System.out.println(cnt);

	}

	public static void combination(int idx, int depth) {

		if (depth == 3) {
			for (int num : result) {
				System.out.print(num + " ");
			}
			System.out.println();
			cnt++;
			return;
		}
		
		//중복순열은 i = 0 부터 탐색 중복조합은 idx만 매개변수로 넘겨준다 딱 그차이 
		for (int i = idx; i < N; i++) {
			result[depth] = Original[i];
			combination(i+1, depth + 1);

		}
	}

}

중복조합

중복조합이란 서로 다른 N개의 원소중에 R개를 뽑는 경우의 수이다 (중복가능)
N개에서 R개를 뽑을 때 순서를 고려하지 않고 단순히 뽑는 모든 경우의 수를 포함한다
1 1 3 4과 같이 중복된 수를 뽑을 수 있지만 1 1 3 4 와 4 3 1 1 은 같은 경우의 수로 취급한다.

중복조합 Java 코드

public class CombinationDup0 {

	static int[] Original = { 100, 200, 300, 400, 500, 600 };
	static int[] result;
	static int N = Original.length;
	static int cnt = 0;

	// 6개중에 3개를 뽑는 조합의 수 (중복o) 6H3 = 8C3 = 8x7x6/3x2x1 = 56
	public static void main(String[] args) {

		result = new int[3];
		combination(0, 0);
		System.out.println(cnt);
	}

	public static void combination(int idx, int depth) {

		if (depth == 3) {
			for (int num : result) {
				System.out.print(num + " ");
			}
			System.out.println();
			cnt++;
			return;
		}
		
		//중복순열은 i = 0 부터 탐색 중복조합은 idx만 매개변수로 넘겨준다 딱 그차이 
		for (int i = idx; i < N; i++) {
			result[depth] = Original[i];
			combination(i, depth + 1);

		}
	}
}

부분집합

부분집합이란 서로 다른 N개에서 R개를 뽑는 경우의 수이다. 조합은 부분집합의 한 부분이라고 볼 수 있다.
-> 특정 갯수 R개에 대한 부분집합 == N에서 R개를 뽑는 경우의 수
부분집합은 0개 부터 N개까지 뽑는 모든 경우의 수에 해당한다

부분집합 Java 코드

public class PowerSet {

	static int[] Original = { 100, 200, 300, 400, 500, 600 };
	static int[] result;
	static boolean[] visited;
	static int N = Original.length;
	static int cnt = 0;

	// 6개 원소를 가지는 집합의 부분집합 2^6 = 128
	public static void main(String[] args) {
		visited = new boolean[N];
		powerSet(0);
		System.out.println(cnt); //공집합 제외 127나오면 정상 

	}

	public static void powerSet(int depth) {
		cnt++;
		
		if(depth == N) {
			for(int i = 0; i < N; i++) {
				if(visited[i]==true) {
					System.out.print(Original[i]+" ");
				}
			}
			System.out.println();
			return;
		}
		
		//부분집합은 for문 쓰지 않는다 쓰면 중복해서 나옴 
		//지금 원소를 포함할 때 
		visited[depth] = true;
		
		//중복 안 되게 idx 늘려준다
		powerSet(depth+1);

		//지금 원소를 포함 안 할 때 
		visited[depth] = false;
		
        //똑같이 중복 안 되게 idx는 늘려준다 
		powerSet(depth+1);

	}

}

갯수별 부분집합 처리

갯수에 해당하는 매개변수를 추가해서 X개를 뽑는 부분집합마다 어떤 Action을 할 수 있다

public class PowerSetDepth {

	static int[] Original = { 100, 200, 300, 400, 500, 600 };
	static int[] result;
	static boolean[] visited;
	static int N = Original.length;
	static int cnt = 0;

	// 6개 원소를 가지는 집합의 부분집합 2^6 = 128
	public static void main(String[] args) {
		visited = new boolean[N];
		powerSet(0, 0);
		System.out.println(cnt); // 공집합 제외 127나오면 정상

	}

	public static void powerSet(int idx, int count) {
		cnt++;

		if (idx == N) {
			return;
		}

		if (count == 2) {
			for (int i = 0; i < N; i++) {
				if (visited[i] == true) {
					System.out.print(Original[i] + " ");
				}
			}
			System.out.println();
		}

		visited[idx] = true;
		powerSet(idx + 1, count + 1);

		visited[idx] = false;
		powerSet(idx + 1, count);

	}
}