순열 (Permutation) - 삽입방식 | (+중복순열, +함수사용)

- 순열 (Permutation) -

 

n개의 수를 중복을 허용하지 않고(visited)

r개를 나열할 수 있는 모든 경우의 수 (1 ≤ r ≤ n)

 

---

 

문제인식)

0부터 9(n)까지의 수가 있다.
이들을 이용하여 4(r)개의 수를 중복없이 나열하고자 할 때
가능한 모든 경우를 각각 한 줄씩 출력하고자 한다면 어떻게 해야할까?

int n=9, r=4;

 

해결과정)

1) 출력에 이용할 배열(a[4]-주황)과 숫자의 중복방지를 위한 방문여부배열(visited[10]-파랑)을 준비한다.
2) 이 배열의 인덱스(idx)마다 0~9까지 삽입하는 반복문을 실행한다. idx는 재귀를 위한 인덱스.
3) 현재 인덱스(idx)에서 사용한 수(i)를 다음 인덱스(idx+1)에서 사용하지 않기 위해 방문처리(visited[i]=1)한다. 그러고나서 다음 인덱스(idx+1)로 재귀진입한다.
4) 인덱스가 나열하고자 하는 수의 갯수(r)를 초과한다면(기저조건) 한 줄씩 출력을 실행한다.
5) 재귀진입이 끝나면 해당 숫자를 다시 사용하기 위해 방문처리를 해제한다.

다음 그림은 재귀가 깊이 한 번 진행되었을 때의 그림을 나타낸 것이다.
주황색 칸은 a배열, 파란색 칸은 visited배열을 나타낸다.

깊은재귀가 한 번 일어날 때의 과정을 묘사한 그림

 

5)번 설명에 대한 설명을 더 하자면,
예를 들어 위 그림에서 "idx+3"에 삽입된 "3"을 방문처리 한 후 다음 재귀는 출력을 진행하고 끝난다.
그렇다면 "idx+2"에서 "3"을 삽입하기 위해선 방문처리했던 "3"을 다시 해제해야 한다.

 

(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

#include <cstdio>

int n=9, r=4;
int a[4];
bool visited[10]; //방문여부배열

void Permutation(int idx) {
    if(idx>=r) {
        //출력 
        for(int i=0; i<r; i++) printf("%d ", a[i]); printf("\n");
        //종료 
        return;
    }

    for(int i=0; i<=n; i++) { //i는 a배열에 삽입하기 위한 수 
        if(visited[i]) continue; //중복방지 
        a[idx]=i;
        visited[i]=true; //재귀진입전 방문처리 
        Permutation(idx+1); //재귀진입
        visited[i]=false;
    }
}

int main() {
    Permutation(0);

    return 0;
}

해당 소스코드를 컴파일, 실행하면
각 줄마다 순열의 경우가 하나씩 오름차순으로 출력하게 된다.

위 코드의 경우 시간복잡도는 당연히 O(n의 r제곱)이다.

 

함수사용)

사실 순열을 탐색하는 방법 중에는
next_permutaion()과 prev_permutation() 함수를 이용하는 방법이 있다. (각각 오름차순, 내림차순)
이 둘은 n개의 수를 r개 고르는 것이 아닌 n개를 완전탐색하는 방식이다.
이 둘을 사용하는 방법은 여기를 참조

 

응용)

백준 문제 - N과 M (1)

 

내림차순으로 출력해보기

중복을 허용하는 순열 출력해보기(사실 더 간단하다.)
(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

#include <cstdio>

int n=9, r=4;
int a[4];

void f(int idx) {
    if(idx>=r) {
        //출력 
        for(int i=0; i<r; i++) printf("%d ", a[i]); printf("\n");
        //종료 
        return;
    }

    for(int i=0; i<=n; i++) { //i는 a배열에 삽입하기 위한 수 
        a[idx]=i;
        f(idx+1); //재귀진입
    }
}

int main() {
    f(0);

    return 0;
}

수를 재귀적으로 삽입하는 방식이 아닌, 재귀적으로 위치를 맞바꾸는 방식으로 해보기

등