재귀를 이용한 간단한 순열 알고리즘

이 소스코드는 중복 요소도 허용한다.

중복 요소를 지우고 싶다면 erase, unique 함수를 이용하면 된다.

중복 요소 제거 방법에 대한 포스팅 링크도 첨부했다.

kimcoder.tistory.com/100?category=887790

벡터 정렬 후, 중복 요소 제거하기

 

순열은 조합과 달리 요소의 순서가 중요할 경우 쓰인다.

순서까지 고려하여 1,2,3,4중 3개를 고르는 경우들이다.

경우의 수는 4P3=24이다.

 

아래에 있는 소스 코드에서 주목할 것은 permutation 함수이다.

순열 함수는 swap 까지 포함하여 15줄 이내로 쉽게 구현 가능하다.

 

소스 코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> arr;

void swap(int *a, int *b ){
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void check(int depth){
	string s ="";
	for(int i=0; i < depth; i++){
		s += (arr[i]+'0');
	}
	cout << s << "\n";		
}

void permutation(int n, int r, int depth){
	if(r == depth){
		check(depth); //arr의 0~r-1 번째 인덱스를 체크하여 출력
		return;
	}
	for(int i=depth; i<n; i++){
		swap(&arr[i], &arr[depth]);
		permutation(n, r, depth+1);
		swap(&arr[i], &arr[depth]);
	}
}

int main() {
	string s;
	s="1234";
	for(int i=0;i<s.length();i++){
		arr.push_back(s[i]-'0');
	}
	permutation(4, 3, 0); //4개 요소들중 3개 선택
}

 

r==depth 일 경우 check후 리턴해주는 과정에 대해 보충 설명 하자면,

check함수에서 arr의 0~r-1번째 인덱스가 출력 대상인데 depth가 r을 넘어 계속 진행 된다면, 요소들이 중복출력 되어버린다. 의미 없는 swap을 방지하기 위한 과정이라고 보면 된다.

(+) 중복출력 실행결과

 

재귀 함수를 쓰는 코드이다보니 직관적으로 이해가 잘 되지 않을 수도 있다.

특히 depth의 개념이 헷갈리다면, depth는 현재 자리까지를 고정해둔다고 이해하면 쉽다.

특정 자리까지를 고정해두고 다음에 이어서 나오는 숫자끼리 permutation을 한다고 생각하면 이해할만할 것이다.