C++ 순열(permutation) - 대학교 컴공 2학년 자료구조 과목

순열이란 무엇인가

순열 P. 우리 고등학교 확통시간에 다 배웠죠? 기억나죠? 하지만 저도 내용은 기억 안나고 그저 배웠다는 사실만 기억나는 타입이기 때문에 이러고 퉁치고 넘어갈 생각은 없습니다. 순열이란, 서로다른 배열요소를 순서를 고려하여 배열하는 경우입니다.

 

예를들어 nPr 이라고 하면, n개의 배열요소 중에 r개를 뽑아 순서를 고려하여 배열하는 경우의 수입니다.

 

수업에 나온 코드 예시

void Permutations(char* a, const int k, const int m) {
	int i;
	if (k == m) {
		for (i = 0; i <= m; i++) 
			cout << a[i] << " ";
		cout << endl;
	}else
		for (i = k; i <= m; i++) {
			swap(a[k], a[i]);
			Permutations(a, k + 1, m);
			swap(a[k], a[i]);
		}
}

코드 구현 방식 설명

배열요소의 시작 인덱스인 k와 끝 인덱스인 m이 같다면, 배열a[]의 배열요소들을 모두 출력한다.

같지 않다면, 

위의 Permutations(char*a, const int k, const int m) 함수는 main 함수 내에서 다음과 같이 사용할 수 있다.

int main(){
char str[]="abc";
int length=strlen(str);

Permutations(str, 0, length-1);

return 0;
}

즉, char*a는 문자열을 가리키는 포인터
k는 첫번째 배열요소의 인덱스 값 즉 0
m은 마지막 배열요소의 인덱스 값, 즉 배열 갯수-1이다.