모든 순열 구하기

순열은 주어진 원소들을 "순서를 신경쓰면서" 일렬로 배열하는 것을 의미한다.

 

n가지 원소의 순열 개수는  n*(n-1)*...*2*1 = n 팩토리얼이다. 이 모든 경우의 수를 찾으려면 빠트리는 경우의 수가 없도록 기준을 정해야 할 것이다.

 

우선 배열의 맨 앞자리를 생각해보자. 배열의 맨 앞자리에는 1~n까지의 모든 수가 올 수 있다. 

1이 가장 먼저 배치되었을때 예시

다음으로 두 번째 자리를 생각해보자. n까지의 수 중 첫 번째 자리에 있는 숫자는 이미 사용했기 때문에 두번째 자리에 올 수는 없다. 따라서 두 번째 자리가 결정되는 경우의 수는 (n-1)이다. 

 

1, 3이 첫번째 두번째 자리에 배치되었을때 예시

같은 방식으로 3번째 자리~n번째 자리까지 배열을 만들면 된다. 자리가 하나 늘어날수록 사용 가능한 숫자가 1씩 줄어들기 때문에 순열의 모든 경우의 수는 n 팩토리얼이라는 값과 딱 맞아 떨어진다.

 

코드로 구현할 때는 재귀함수를 이용하면 될 것 같다. 그리고 어떤 숫자가 배열에서 이미 사용되었는지를 인자로 같이 전달해주면 될 것 같다. 코드로 한번 구현해보았다.

 

[전체 코드]

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

void print(int* arr, int N) { //출력 함수
	for (int* p = arr; p < arr + N; p++) {
		printf("%d ", *p);
	}
	printf("\n");
}
int check(int* exists, int n) { // 이미 사용된 수인지 체크
	if (exists[n- 1] == 1)
		return 0;
	else
		return 1;
}
void permutation(int* arr, int* exists, int N,int max_index, int index) { // 수열 배열 재귀함수
	if (max_index == index) {
		print(arr, max_index); //배열 한세트가 완성되었을때 출력
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (check(exists, i)) {
				arr[index] = i;
				exists[i - 1] = 1; //숫자 i를 조합에 사용했다는 것을 기록하기 위함 
				permutation(arr, exists, N, max_index, index + 1);
				exists[i - 1] = 0; //index번째 원소에 대한 조합이 완료되었으므로 해당 숫자를 사용 해제 처리
			}
		}
	}
}

int main() {
	int* arr; //순열이 임시 저장될 배열
	int* exists; //사용된 숫자 정보가 들어갈 배열

	int N;
	int M;
	scanf("%d %d", &N, &M); //문제에서 주어진 N, M 입력
	arr = (int*) calloc(M, sizeof(int)); 
	exists = (int*)calloc(N, sizeof(int)); 
	permutation(arr, exists, N,M, 0); //모든 순열 구하기
}

역시 주석으로 상세히 설명하는게 훨씬 편하다..

 

※ 만약 여기서 조합을 모두 구하라고 하면 어떻게 해야할까?

 

조합은 순서를 고려하지 않는다는 점에서 순열과 차이가 있다. 따라서 조합을 이루고있는 구성 숫자들이 같은 경우는 단 하나만 있어야 한다.(순열은 구성 숫자들이 같아도 순서가 다르면 다른 경우의 수임)

 

따라서 다음과 같이 숫자들이 오름차순으로만 구성되도록 코드를 살짝 변경해주면 모든 조합의 경우를 구할 수 있다.

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

void print(int* arr, int N) { //출력 함수
	for (int* p = arr; p < arr + N; p++) {
		printf("%d ", *p);
	}
	printf("\n");
}
int check(int* exists, int n) { // 이미 사용된 수인지 체크
	if (exists[n- 1] == 1)
		return 0;
	else
		return 1;
}
void permutation(int* arr, int* exists, int N,int max_index, int index, int prev_num) { // 수열 배열 재귀함수
	if (max_index == index) {
		print(arr, max_index); //배열 한세트가 완성되었을때 출력
	}
	else {
		for (int i = prev_num + 1; i <= N; i++) { //오름차순으로 정렬 되었을때만 출력함(숫자끼리 순서만 바꾸는것 방지)
			if (check(exists, i)) {
				arr[index] = i;
				exists[i - 1] = 1; //숫자 i를 조합에 사용했다는 것을 기록하기 위함 
				permutation(arr, exists, N, max_index, index + 1, i);
				exists[i - 1] = 0; //index번째 원소에 대한 조합이 완료되었으므로 해당 숫자를 사용 해제 처리
			}
		}
	}
}

int main() {
	int* arr; //조합이 임시 저장될 배열
	int* exists; //사용된 숫자 정보가 들어갈 배열

	int N;
	int M;
	scanf("%d %d", &N, &M); //문제에서 주어진 N, M 입력
	arr = (int*) calloc(M, sizeof(int)); 
	exists = (int*)calloc(N, sizeof(int)); 
	permutation(arr, exists, N,M, 0, 0); //모든 조합 구하기
}