C语言 |
您所在的位置：网站首页 › 全排列递归算法C语言 › C语言 |
C语言
|
全排列
简介
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 公式：全排列数f(n)=n!(定义0!=1)，如1,2,3三个元素的全排列为： 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 共3 * 2 * 1 = 6 种。 分析
由图可以看出可以利用分治法，先依次取出一项元素，然后将剩下的几个元素继续按照元素依次取出，直至剩下最后一项元素，然后依次打印。 比如：abcd --> 【a】【bcd】 --> 【a】【b】【cd】 --> 【a】【b】【c】【d】–>打印。然后回到上一个序列，【a】【b】【cd】 --> 【a】【 b】【d】【 c】 -->打印… 网上流传甚广的交换法就是用的这种算法。 代码 #include void Perm(int list[],int k,int m)//k表示前缀的位置,m是数组的长度. { if(k==m-1)//前缀是最后一个位置,此时打印排列数. { for(int i=0; i //交换前缀,使之产生下一个前缀. Swap(&list[k],&list[i]); Perm(list,k+1,m); //将前缀换回来,还原成上一个的前缀排列. Swap(&list[k],&list[i]); } } //交换函数 void Swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp; } int main(int argc, char *argv[]) { int a[]= {1,2,3,4}; Perm(a,0,4); } 字典序基于字典排序的方法，生成给定全排列的下一个排列，并保证后一个排序在前一个排序的后面。以上的代码会有一个问题，就是在交换数据的时候，会破坏原有的顺序，比如： 原始序列 1,2,3 ，在1和3交换的时候，会产生一个3,2,1的排序，并且会被率先打印出来。最后的结果会是 ：123、132、213、231、321、312 。 找到了原因那问题就很容易被解决了。比如：当生成【3】【21】当生成一个前缀和一个子序列时，先对子序列排序就行了。变成【3】【12】即可。在原来的代码上加入排序，写法很简单。【注：非正规冒泡，这种写法挺有趣，效率至少不低于正规冒泡】。 #include void Perm(int list[],int k,int m)//同上 { if(k==m-1) { for(int i=0; i //非正规冒泡排序--实现字典序 for(int i = k ; i Swap(&list[k],&list[i]); Perm(list,k+1,m); Swap(&list[k],&list[i]); } } } void Swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp; } int main(int argc, char *argv[]) { int a[]= {1,1,2,3}; Perm(a,0,4); } 去重问题如果全排列中，数字有重复，比如三个1组成的序列【111】，很显然排列只有一种，不需要交换。 解决思路就是在交换前检查待交换的元素是否相等即可。在字典序的基础增加一点判断，如下： #include void Perm(int list[],int k,int m)//k表示前缀的位置,m是数组的长度. { if(k==m-1)//前缀是最后一个位置,此时打印排列数. { for(int i=0; i //冒泡排序--实现字典序 for(int i = k ; i if( list[k] != list[i] || i == k) //值不相等则交换 以及 i == k 要交换 { //交换前缀,使之产生下一个前缀. Swap(&list[k],&list[i]); Perm(list,k+1,m); //将前缀换回来,继续做上一个的前缀排列. Swap(&list[k],&list[i]); } } } } //交换函数,用函数写，思路会清晰很多。 void Swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp; } int main(int argc, char *argv[]) { int a[]= {1,1,2,3}; Perm(a,0,4); } 总结分治法的实现模式可以是递归方式，也可以是非递归方式，一般采用递归方式的算法模式。从算法的角度看，分治法得到的子问题和原问题是相同的，当然可以用相同的函数来解决，区别只在于问题的规模和范围不同。 |
【本文地址】
今日新闻 |
推荐新闻 |