순열

순열(Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다.
• 순서O, 중복 X

nPr

• 그리고 nPr은 다음과 같은 식이 성립한다.

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

• nPn = n! 이라고 표현하며 Factorial이라 부른다.

n! = n * (n-1) * (n-2) * … * 2 * 1

• 다수의 알고리즘 문제들을 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 있다.
  • 예) TSP(Traveling Salesman Problem)
• N 개의 요소들에 대해서 n! 개의 순열들이 존재한다.
  • 12! = 479,001,600
  • n > 12 인 경우, 시간 복잡도 폭발적으로 UP
  • 10! 까지만 쓰고 11! 을 쓴다면 백트리킹을 섞어 쓰자

반복문 중복 순열

• 순서O, 중복O

for (int i = 0; i <N; i++) {			//첫번째 원소 선택
	for (int j = 0; j <N; j++) {		//두번째 원소 선택
		for (int k = 0; k <N; k++) {	//세번째 원소 선택
			System.out.printf("%d %d %d%n", data[i], data[j], data[k]);
		}
	}
}

반복문 순열

• for문을 통해 순열을 구할때 문제점
• 원소수 N은 가변이지만 선택한 R개는 고정이 됨
• 재귀호출을 통해 R개를 가변적으로 선택할 수 있다.
• 순서O, 중복 X

for (int i = 0; i <N; i++) {			//첫번째 원소는 다 선택
	for (int j = 0; j <N; j++) {		//두번째 원소 선택
		if(i !=j ) {					//첫번째 원소와 중복 되는 원소는 제거 
			for (int k = 0; k <N; k++) {//세번째 원소 선택
				if(i!=k && j!=k) {		//첫번째 원소와 두번째 원소와 중복 되는 원소 제거
					System.out.printf("%d %d %d%n", data[i], data[j], data[k]);
				}
			}
		}
	}
}

재귀 중복 순열

• 서로 다른 n개 중 r개를 중복해서 선택하는 순열
• 순서O, 중복O

//기저 - 유도로 구한 경우 
public static void permutation(int depth) {
	//배열은 0부터 시작하므로 R-1개가 모든 원소를 뽑은 상황. 
	//depth가 R과 동일한 상황은 순열 하나의 모든 원소를 다 뽑은 상황 
	if(depth == R) {
		//순열을 뽑은 이후의 task를 작성한다. 
		return;
	}
    
	//원소를 선택
	for (int i = 0; i <N; i++) {
		numbers[depth] = input[i];
		permutation(depth+1);
	}
}

재귀 순열 1

//기저 - 유도로 구한 경우 
public static void permutation(int depth) {
	//배열은 0부터 시작하므로 R-1개가 모든 원소를 뽑은 상황. 
	//depth가 R과 동일한 상황은 순열 하나의 모든 원소를 다 뽑은 상황 
	if(depth == R) {
    	//순열을 뽑은 이후의 task를 작성한다. 
		return;
	}
		
	//원소를 선택
	top:
	for (int i = 0; i <N; i++) {
		//중복 검사
		for (int j = 0; j < depth; j++) {
			if(numbers[j] == input[i]) {  //중복된 경우 
				continue top;
			}
		}
		numbers[depth] = input[i];
		permutation(depth+1);
	}
}

재귀 순열 2

• isSelected 배열을 이용하여 해당 인덱스의 요소가 선택 되었는지 판별
• 사전식 순열을 구할 수 있다.

//기저 - 유도로 구한 경우 
public static void permutation(int depth) {
	//배열은 0부터 시작하므로 R-1개가 모든 원소를 뽑은 상황. 
	//depth가 R과 동일한 상황은 순열 하나의 모든 원소를 다 뽑은 상황 
	if(depth == R) {
		//순열을 뽑은 이후의 task를 작성한다. 
		return;
	}
	
	//원소를 선택
	for (int i = 0; i <N; i++) {
		//중복 검사
		if(isSelected[i]) continue;
		numbers[depth] = input[i];
		isSelected[i] = true;
		permutation(depth+1);
		isSelected[i] = false;
	}
}

재귀 순열 3

• flag를 이용해서 재귀 순열을 구현
• 비트 마스킹을 이용해서 flag에 해당 요소가 선택 되었는지 판별

//기저 - 유도로 구한 경우 
public static void permutation(int depth, int flag) {
	//배열은 0부터 시작하므로 R-1개가 모든 원소를 뽑은 상황. 
	//depth가 R과 동일한 상황은 순열 하나의 모든 원소를 다 뽑은 상황 
	if(depth == R) {
		//순열을 뽑은 이후의 task를 작성한다. 
		return;
	}
		
	//원소를 선택
	for (int i = 0; i <N; i++) {
		//중복 검사
		if((flag  & 1<< i) !=0) continue;
		numbers[depth] = input[i];
		permutation(depth+1,  flag | 1<<i);
	}
}

재귀 순열 4

• swap을 이용해서 재귀 순열을 구현
• 순열들의 순서가 보장되지 않는다.

//기저 - 유도로 구한 경우 
public static void permutation(int depth) {
	//배열은 0부터 시작하므로 R-1개가 모든 원소를 뽑은 상황. 
	if(depth == R-1) {
		//순열을 뽑은 이후의 task를 작성한다. 
		return;
	}
		
	//원소를 선택
	for (int i = depth; i <N; i++) {
		swap(i, depth);
		permutation(depth+1);
		swap(i, depth);
		}
	}
    
private static void swap(int i, int depth) {
	int temp = input[i];
	input[i] = input[depth];
	input[depth] = temp;
}