[알고리즘] 순열 (Permutation)

mallin·2022년 1월 15일

알고리즘

목록 보기

1/9

n개의 값 중에서 r 개의 숫자를 순서를 고려해 나열한 경우의 수

nPr = n x n-1 x n-2 ...... x n-r+1
EX) {1,2,3} 총 3개의 값 중에서 3개의 숫자를 순서를 고려해 나열하면
1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1 로 총 6개 로 나타낼 수 있다 (3! = 1x2x3)

1. Swap 을 이용한 순열

swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법
배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap

🤝 과정

0번째 인덱스 원소를 0번째 부터 n-1번째까지 위치를 바꾼다 (ABC, BAC, CBA)
1번 과정을 진행해서 나온 경우들을, 1번째 인덱스 원소를 1번째부터 n-1번째까지 위치를 바꾼다
이러한 과정을 n-1번 반복한다

🌟 주의할 점

순열들의 순서가 보장되지 않는다 EX) C,A,B 가 먼저 나오는 게 아니라 C,B,A 가 먼저 노출됨

📝 구현 (c++)

#include <stdio.h>
void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
void perm(int arr[], int depth, int n, int k) {
    if (depth == k) {
        for(int i=0;i<n;i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
        return;
    }
    
    for(int i = depth; i < n;i++) {
        swap(arr, i, depth);				// 배열을 depth 에 따라 변경 
        perm(arr, depth+1, n, k); 			// 재귀 함수 
        swap(arr, i, depth); 				// 변경된 배열을 다시 원복
    }
}
int main() {
    int arr[] = {1,2,3};
    perm(arr, 0, sizeof(arr) / 4 ,2);
    
    return 0;
}

변수	설명
arr	순열 알고리즘 적용할 배열
depth	현재 깊이
n	배열 안에 들어 있는 숫자 갯수 (고정)
k	몇 depth 까지 보여줄지 설정 (고정)

2. Visited 배열을 이용한 순열

visited 변수 사용
DFS = 깊이 우선 탐색, 한 노드의 자식을 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가면서 순회

🤝 과정

DFS를 돌면서 모든 인덱스에 방문해 output 배열에 값을 넣는다
이미 들어간 값은 visited 를 true 로 변경해서 중복해서 값이 들어가지 않도록 한다
이러한 과정을 depth 가 r 값과 같아질 때까지 반복한다

📝 구현 (c++)

#include <stdio.h>
void perm(int arr[], bool visited[], int output[], int depth, int n, int k) {
    
    if (depth == k) {
        for(int i=0;i<n;i++) {
            printf("%d ", output[i]);
        }
        printf("\n");
        return;
    }
    
    for (int i=0;i<n;i++) {
        if (visited[i] != true) {
            visited[i] = true;
            output[depth] = arr[i];
            perm(arr, visited, output, depth + 1, n, k); // 재귀 함수 
            visited[i] = false;	// 중복 확인 배열 
        }
    }
    
}
int main() {
    int n = 3;
    int arr[] = {1,2,3};
    bool visited[n];
    int output[n];
    
    perm(arr, visited, output, 0, n, 3);
}