길이 n의 순열은 숫자 1, 2, ..., n이 반복되지 않는 정렬된 모음입니다. 예를 들어 [3, 1, 2]와 [5, 4, 3, 2, 1]은 순열이지만 [1, 2, 1, 3]과 [1, 2, 4]는 순열이 아닙니다.
작업이 길이 n의 모든 순열을 반복해야 한다는 사실로 축소되면 "next_permutation"이라고 하는 C++의 편리한 메커니즘을 사용할 수 있습니다.
문서에서 자세히 알아볼 수 있지만 요점은 이 함수가 전달된 배열을 변경한다는 것입니다. 사전식 순서(일반적으로 명확하고 이름이 명확함)의 후속 순열로.
next_permutation을 사용하려면 알고리즘 라이브러리를 포함해야 합니다(예: 프로그램 시작 부분에 #include <algorithm> 작성)
예:
vector 어러;
도착 = {1, 2, 3}; // 배열은 [1, 2, 3]입니다.
next_permutation(arr.begin(), arr.end()); // 전체 배열을 함수에 전달
// 배열은 이제 [1, 3, 2]입니다.
도착 = { 2, 3, 1 }; // 배열은 [2, 3, 1]입니다.
next_permutation(arr.begin(), arr.end()); // 전체 배열을 함수에 전달
// 배열은 이제 [3, 1, 2]입니다.
next_permutation(arr.begin() + 1, arr.begin() + 3); // 배열의 일부에 함수를 적용할 수 있지만 실제로는 거의 필요하지 않습니다.
// 배열은 이제 [3, 2, 1]입니다.
이 경우 함수는 다음 순열이 생성되면 true이고 다음 순열이 없으면 false인 부울 반환 값을 갖습니다(사전식 순서의 최대 순열이 함수에 전달되는 경우).
이렇게 하면 루프에서 함수를 사용할 수 있으므로 모든 순열을 한 번에 반복할 수 있습니다. 0-인덱싱으로 인해 순열에는 공식적으로 1에서 n까지의 숫자가 포함되지만 실제로는 0에서 n - 1까지의 숫자 순열로 작업하는 것이 더 편리한 경우가 많습니다. 그러나 다행스럽게도 이것은 코드에서 추가 오버레이로 이어지지 않습니다. next_permutation 함수는 인덱스가 0인 순열에 맞게 조정됩니다(및 배열의 중복 요소도 있지만 더 많은 정보를 직접 찾을 수 있음).
일반적으로 모든 순열을 반복하는 코드는 다음과 같습니다.
정수; // 순열 크기
vectorperm(n); // perm은 "순열"의 줄임말입니다. "순열"
for (int i = 0; i < n; i++)
perm[i] = i; // 초기 순열 0, 1, ..., n - 1 초기화
하다 {
// 루프 내부에서 현재 순열을 처리합니다.
} 동안 (next_permutation(perm.begin(), perm.end())); // 다음 순열이 없으면 루프를 종료합니다.
이 코드는 O(n! * f(n))에서 실행됩니다. 여기서 f(n)은 하나의 특정 순열을 처리하는 데 걸리는 시간입니다.
|