문제 26
순열 출력하기
$1$부터 $N$까지의 정수 중 서로 다른 $M$개를 골라 만들 수 있는 모든 순열을 출력하라.
순열은 사전 순으로 출력한다.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le M \le N \le 8)$
출력
만들 수 있는 모든 순열을 사전 순으로 출력한다.
각 순열은 하나의 줄에 출력하며 순열을 이루는 수는 공백으로 구분한다.
예제 입력 1
4 2
예제 출력 1
1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3
공식 해설
$N\le8$이므로 요구한 순열들을 직접 생성할 수 있다. 다만 사전 순으로 출력해야 하므로 앞자리에서 작은 수를 선택한 경우부터 탐색한다.
순열의 앞자리부터 아직 쓰지 않은 수를 하나씩 선택하는 백트래킹을 사용한다. 현재 순열과 각 수의 사용 여부를 저장하고, 길이가 $M$이 되면 한 줄 출력한다.
각 자리에서는 $1$부터 $N$까지 작은 수부터 확인한다. 한 수를 넣어 뒷자리를 모두 탐색한 다음 그 수를 빼고 사용 표시를 되돌린다. 그러면 서로 다른 $M$개의 수로 이루어진 모든 순열이 정확히 한 번 생성된다.
두 순열의 순서가 처음 달라지는 자리에서 더 작은 수를 고른 경우를 먼저 탐색하므로 출력 순서도 사전 순이다. 결과를 모아 다시 정렬할 필요가 없다.
순열의 개수를 $P=N!/(N-M)!$라 하자. 각 재귀 호출에서 $N$개 후보를 확인하는 구현의 시간복잡도는 $O(NP)$이며 출력 자체에 $O(MP)$가 필요하다. 사용 여부와 현재 순열을 저장하는 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
현재 순열은 vector<int>, 사용 여부는 크기 $N+1$의 배열로 둔다. 재귀 호출 전후에 push_back과 pop_back, 사용 표시와 해제를 짝지어 수행한다. 길이가 $M$이면 즉시 출력하고 돌아온다.
C 구현
used[9]와 길이 $M$의 path 배열을 두고 $1$부터 $N$까지 순서대로 선택하는 DFS를 작성한다. $M$개를 채우면 즉시 출력하고 돌아온 뒤 used 표시를 지운다.
Python 구현
itertools.permutations(range(1, N + 1), M)을 순회하면서 각 순열을 출력한다. 입력 iterable이 오름차순이므로 출력도 사전순이다.
Java 구현
boolean[] used와 int[] path를 재귀 DFS에 전달한다. 완성된 순열은 BufferedWriter로 출력한다.
Rust 구현
used 배열과 path Vec을 DFS 함수에 전달한다. 선택 시 push하고 복귀 시 pop한 뒤 used를 해제한다.
JavaScript 구현
길이 $M$의 현재 순열과 Uint8Array(n + 1) 사용 표시를 두고 백트래킹한다. 각 깊이에서 $1$부터 $N$까지 순서대로 넣고, 재귀 호출 뒤 pop()과 사용 표시 해제를 수행한다.
완성된 순열은 path.join(' ')으로 한 줄을 만든다. 출력량이 많으면 줄들을 적당한 크기로 모아 비운다.