[C++] 재귀함수로 순열 구현하기 코드

1. nPn (nPk 에서 n＝k인 경우)

 

#include <iostream>
using namespace std;

int arr[] = { 1, 2, 3, 4 };

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

void print_array() {
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
		cout << arr[i] << " ";
	cout << endl;
}

void permutation(int n, int r) {
	if (r == 0) { print_array(); return; }
	for (int i = n - 1; i >= 0; i--) {
		swap(&arr[i], &arr[n - 1]);
		permutation(n - 1, r - 1);
		swap(&arr[i], &arr[n - 1]);
	}
}

int main() {
	permutation(sizeof(arr) / sizeof(int), sizeof(arr) / sizeof(int));
	return 0;
}

 

 

2. nPk 에서 n≠k 인 경우)

 

#include <iostream>
using namespace std;

int arr[] = { 1, 2, 3, 4 };

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

void print(int size) {
	for (int i = 0; i < size; i++) printf("%d ", arr[i]);
	printf("\n");
}

void permutation(int n, int r, int depth) {

	if (r == depth) { print(depth); 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() {
	permutation(sizeof(arr) / sizeof(int), 3, 0);
	return 0;
}