工学1号馆

home

« | 返回首页 | »

全排列的生成算法–基础的回溯递归

By Wu Yudong on August 21, 2018

全排列算法解决思路:假设现有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;
}

 

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)