순열(Permutation)

순열?

순열이란 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것을 말한다.

 

서로 다른 n개 중 r개를 택하는 순열은 nPr로 표현한다.

nPr = n * (n-1) * (n-2) * ... * (n-r+1)    (r개의 곱)

nPn = n!

 

완전 검색 포스팅에서도 말했지만, 12!의 경우 거의 4억8천만번의 연산을 하기 때문에 n이 12를 넘어가면 연산 양이 엄청나게 많아진다.

---

순열 vs 조합

순열과 조합은 선택한 요소들의 순서가 의미가 있는지 여부로 구분된다.

 

순서의 의미가 다르다면 순열, 같다면 조합이다.

즉, 123과 321을 구분한다면 순열, 구분하지 않는다면 조합이다.

 

예를 들어, 이어달리기 사람 뽑는건 순서 의미가 있으므로 순열

농구 참가자 뽑는건 순서 의미가 없으므로 조합이다.

---

순열 구현 - 반복문

1, 2, 3중 3개를 택할 수 있는 경우를 따진다. 즉, 3P3을 구해본다.

코드

결과

---

순열 구현 - 재귀

코드

결과

---

전체 코드

import java.util.Arrays;

public class Main {

	static int N = 3;
	static int R = 3;
	
	static int[] input = {1, 2, 3};					// n개 원소 가진 배열
	
	// nPr에서 n = 3, r = 3일 때이다.
	// for문의 중첩은 r만큼 들어간다.
	static void permutation_for() {
		for(int i = 0; i < N; i++) {
    		for(int j = 0; j < N; j++) {
    			if(j != i) {
    				for(int k = 0; k < N; k++) {
    					if(k != i && k != j) {
    						System.out.println(input[i] + " " + input[j] + " " + input[k]);
    					}
    				}
    			}
    		}
    	}
	}
    
	static int[] numbers = new int[R];				// 순열이 저장될 배열(r만큼)
	static boolean[] isSelected = new boolean[N];	// 사용한 숫자인지 확인하는 배열

	static void permutation_recursive(int cnt) {	// 현재까지 뽑은 순열 원소 갯수
		if(cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i = 0; i < N; i++) {
			if(isSelected[i]) {
				continue;
			}
			
			numbers[cnt] = input[i];
			isSelected[i] = true;
			permutation_recursive(cnt+1);
			isSelected[i] = false;
		}
	}
	
    public static void main(String[] args) {
    	
    	permutation_for();
    	
    	System.out.println();
    	
    	permutation_recursive(0);
    	
    }
    
}