BOJ 10974 · 모든 순열

알고리즘 분류 : 브루트 포스  

C++ STL의 algorithm에 구현되어 있는 next_permutation 함수를 사용하면 된다.

next_permutation 구현은 다음 글을 참조.

---

C++ 소스코드

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i=0; i<n; i++) a[i] = i+1;
    do {
        for (int i=0; i<n; i++) printf("%d ", a[i]);
        printf("\n");
    } while (next_permutation(a, a+n));
    return 0;
}

---

Python 3 소스코드

def next_permutation(a):
    n = len(a) - 1
    i = n
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i == 0:
        return False
    j = n
    while a[i-1] >= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = n
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

a = [i+1 for i in range(int(input()))]
while True:
    print(' '.join(map(str, a)))
    if next_permutation(a) is False:
        break

---

참고

• 백준 온라인 저지 : BOJ 10974
• 다음 순열
• 위키피디아 : 순열