-
[Algorithm] 순열 조합Programming 2016. 10. 23. 02:46
본 글은 아래 블로그에서 참고하여 재정리한 글임을 먼저 밝힙니다.
고락고락 닷컴님의 순열(Permutation) 알고리즘
http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/
알고리즘 문제를 풀다보면 다음과 같이 N개의 숫자 중 R개의 숫자를 골라서 만들어낼 수 있는 모든 조합을 구해야 하는 경우가 종종 있다.
ㅁ 4개의 숫자
1, 2, 3, 4
ㅁ 4개의 숫자 중 4가지 숫자로 만들어낼 수 있는 조합 (중복을 허용하지 않음)
1, 2, 3, 4
1, 2, 4, 3
1, 3, 2, 4
1, 3, 4, 2
...
출처 : http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/
중요한 포인트는, 각 노드에서 스위칭된 원소는 Fixed되어 버리고, Fixed된 원소를 제외한 나머지 원소에 대해 다시 스위칭을 하면서 자식 노드를 뻗어 내려간다는 것이다. (더 이상 스위칭할 원소가 없을때까지)
C++ 버전으로 재작성한 코드
#include <iostream> #define MAX 4 using namespace std; void swap(int arr[MAX], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void print(int arr[MAX], int k) { for (int i = 0; i < k; i++) { if (i == k - 1) { cout << arr[i] << endl; } else { cout << arr[i] << ","; } } } void perm(int arr[MAX], int currentDepth, int n, int k) { if (currentDepth == k) { print(arr, k); return; } for (int i = currentDepth; i < n; i++) { swap(arr, i, currentDepth); perm(arr, currentDepth + 1, n, k); swap(arr, i, currentDepth); } } int main(void) { int arr[MAX] = { 1, 2, 3, 4 }; int totalOfElement = MAX; int outputOfElement = MAX; perm(arr, 0, totalOfElement, outputOfElement); return 0; }
C++ STL 활용
#include <iostream> #include <algorithm> #define MAX 4 using namespace std; int main(void) { int arr[MAX] = { 1, 2, 3, 4 }; do { for (int i = 0; i < MAX; i++) { cout << arr[i] << ","; } cout << endl; } while (next_permutation(arr, arr + MAX)); return 0; }
'Programming' 카테고리의 다른 글
[Android] 피카소(Picasso) 라이브러리 소개 및 주의할 점 (0) 2017.09.23 [Android] Asset Studio 활용하여 해상도별 Launcher Icon 세팅하기 (0) 2017.01.08 [Android] Play Store 업데이트, zipalign 사용법 (1) 2016.12.12 [Algorithm] 부분 집합(power set) (1) 2016.10.26