jasonbla

[Algorithm] 순열 조합 본문

Programming

[Algorithm] 순열 조합

jason jason hwang 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;
}
0 Comments
댓글쓰기 폼