Wu Yudong's Blog

全排列算法解决思路：假设现有1 2 3 三个数，我们构造全排列的方式为：先确定第一位1，然后可选（2，3）（3，2）作为后序的排列组合，这样以1作为首位的全排列就有（1，2，3）（1，3，2）两种，然后再以2作为第一位，从而构造出（2，1，3）（2，3，1）, 最后是（3，1，2）（3，2，1）。即求n个数的全排列=先枚举确立一个数，然后求n-1的全排列。这与我们常见的回溯递归法基本一样。当所有的位数都确定完毕，即成为一组完整的排列数，也就是递归的出口。

// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

int Count = 0;

void Swap(int *a, int *b)
{
	int t;
	t = *a;
	*a = *b;
	*b = t;
}

//输出A数组前n位
void Print(int A[], int n)
{
	for (int i = 0; i < n; i++) {
		printf("%d%c", A[i], i == n - 1 ? '\n' : ' ');
	}
}

void Permutation(int A[], int m, int n)
{
	if (m == n) {
		Print(A, n);
		Count++;
	} else {
		for (int i = m; i < n; i++) {
			Swap(&A[m], &A[i]);
			Permutation(A, m + 1, n);
			Swap(&A[m], &A[i]);
		}
	}
}

int main()
{
	int array[] = { 1, 2, 3, 4 };
	int n = sizeof(array) / sizeof(array[0]);
	int begintime, endtime;
	begintime = clock();		//计时开始
	Permutation(array, 0, n);
	endtime = clock();			//计时结束
	printf("%d\n", Count);
	printf("Running Time: %dms\n", endtime - begintime);
	return 0;
}