1. 순열 (Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 nPr로 표현한다.
  • nPr = n * (n-1) * (n-2) * … * (n-r+1)
  • nPn = n!
    • n! = n * (n-1) * … * 2 * 1
• 서로 다른 N개의 원소들을 순서를 고려하여 나열하는 경우의 수
• 순열은 순서를 고려하기 때문에, 해당 숫자가 이전에 사용된 적 있는지 반드시 확인해야 한다!

“반복문을 통한 순열 구현”

• {1, 2, 3}을 포함하는 모든 순열을 생성

private static void permutation() {
	for(int i=1; i<=3; i++) {
		for(int j=1; j<=3; j++) {
			if(j != i){
				for(int k=1; k<=3; k++) {
					if(k != i && k != j)
						System.out.println(i + " " + j + " " + k);
				}
			}
		}
	}
}

“재귀를 통한 순열 구현”

• {1, 2, 3}을 포함하는 모든 순열을 생성

static int N = 3;
static int[] numbers = new int[N];
static boolean[] isSelected = new boolean[N];

public static void permutation(int cnt) {
	
	if(cnt == N){
		for(int i=0; i<N; i++)
			System.out.print(numbers[i] + " ");
		System.out.println();
		return;
	}

	for(int i=0; i<N; i++) {
		if(!selected[i]){
			selected[i] = true;
			numbers[cnt] = cnt + 1;
			permutation(i+1);
			selected[i] = false;
		}
	}	
}

• 중복을 허용한 순열 (방문 처리를 하지 않아도 된다.)

static int N = 3;
static int[] numbers= new int[N];
static boolean[] isSelected = new boolean[N];

public static void permutation(int cnt) {

	if(cnt == N) {
		for(int i=0; i<N; i++)
			System.out.print(numbers[i] + " ");
		System.out.println();
		return;
	}

	for(int i=0; i<N; i++) {
		numbers[i] = i+1;
		permutation(cnt+1);
	}
}

2. 조합 (Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것
• 순서가 없기 때문에, 이전에 해당 번호를 사용한 적 있는지 확인할 필요가 없다.
• nCr로 표현