[기초 알고리즘] 수학: 순열

1. Permutation

• 집합의 원소들을 모두 사용하여 순서를 고려하여 배열한 모든 경우의 수

 

전단사 함수

• 정의역과 공역이 같습니다.

 

순열의 수

• ${\displaystyle n!=n(n-1)(n-2)\cdots \cdot 2\cdot 1}$

 

예

좌석 배치

(1,2,3,4)	(2,1,3,4)	(3,1,2,4)	(4,1,2,3)
(1,2,4,3)	(2,1,4,3)	(3,1,4,2)	(4,1,3,2)
(1,3,2,4)	(2,3,1,4)	(3,2,1,4)	(4,2,1,3)
(1,3,4,2)	(2,3,4,1)	(3,2,4,1)	(4,2,3,1)
(1,4,2,3)	(2,4,1,3)	(3,4,1,2)	(4,3,1,2)
(1,4,3,2)	(2,4,3,1)	(3,4,2,1)	(4,3,2,1)

 

 

2. K-Permutation

• 서로 다른 n개의 원소 가운데 유니크한 k개를 골라서 만든 순열

 

순열의 수

• ${\displaystyle P(n,r)=n(n-1)\cdots (n-r+1)}$

 

코드

private void perm(int k, int depth) {
    if (depth == k) {
        System.out.println(Arrays.toString(choosed));
        return;
    }

    for (int i = 0; i < src.length; i++) {
        if (visited[i]) continue;

        visited[i] = true;
        choosed[depth] = src[i];
        perm(k, depth+1);
        visited[i] = false;
    }
}

 

예

• 경영진 선출
• 발표 순서 결정

 

3. Duplicate Permutation

• 서로 다른 n개의 원소 가운데 k개를 고르고, 중복을 허용하여 만든 순열

 

순열의 수

• ${\displaystyle _{n}\Pi _{r}} = {\displaystyle n^{r}}$

 

코드

private void permDup(int k, int depth) {
    if (depth == k) {
        System.out.println(Arrays.toString(choosed));
        return;
    }

    for (int i = 0; i < src.length; i++) {
        choosed[depth] = src[i];
        permDup(k, depth+1);
    }
}

 

예

음료 주문

• 6명이 4종류의 음료 주문 (오미자차, 감잎차, 둥굴레차, 국화차)
• $4^6$

 

4. Next Permutation

• 주어진 순열에서 사전순으로 바로 다음에 오는 순열을 찾는 알고리즘

 

동작 원리

피벗 찾기

• 뒤에서부터 가장 긴 감소하는 부분 찾기
• 끝에서부터 왼쪽으로 탐색하며, 처음으로 감소하는 부분을 찾음
• 해당 숫자에서 한칸 앞 숫자 선택

 

피벗보다 큰 값 찾기

• 피벗의 오른쪽 부분에서 피벗보다 큰 숫자 중 가장 작은 숫자 찾기
• 오른쪽 끝에서 순서대로 가장 먼저 발견한 수 선택

 

교환 (피벗과 피벗보다 큰 수)

피벗 위치 뒤쪽을 정렬 (오름차순)

• 피벗 뒤는 내림차순으로 정렬되어 있으므로 오름차순 숫자가 됨 (중앙을 기준으로 뒤집기)

 

코드

public boolean np() {
    int i = arr.length-1;    
    while (i >= 0 && arr[i] <= arr[i-1]) i--;

    if (i == 0) return false;
    
    int pivot = i-1, j = arr.length-1;
    
    while (arr[pivot] >= arr[j]) j--;
        
    swap(pivot, j);
    
    filp(pivot+1, arr.length-1);
    
    return true;
}

 

 

출처

• Wiki - Permutation