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】 -->打印…
⽹上流传甚⼴的交换法就是⽤的这种算法。
代码
void Perm(int list[],int k,int m)//k表⽰前缀的位置,m是数组的长度.
{
if(k==m-1)//前缀是最后⼀个位置，此时打印排列数.
{
for(int i=0; i<m; i++)
{
printf("%d",list[i]);
}
printf("\n");
return;
}
for(int i = k; i < m; 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】即可。在原来的代码上加⼊排序，写法很简单。【注：⾮正规冒泡，这种写法挺有趣，效率⾄少不低于正规冒泡】。
void Perm(int list[],int k,int m)//同上
{
if(k==m-1)
{
for(int i=0; i<m; i++)
{
printf("%d",list[i]);
}
printf("\n");
return;
}
else
{
//⾮正规冒泡排序--实现字典序
for(int i = k ; i < m-1; i++)
for(int j = k+1; j < m; j++)
{
if(list[i]> list[j])
Swap(&list[i],&list[j]);
}
for(int i = k; i < m; 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】，很显然排列只有⼀种，不需要交换。  解决思路就是在交换前检查待交换的元素是否相等即可。在字典序的基础增加⼀点判断，如下：
void Perm(int list[],int k,int m)//k表⽰前缀的位置,m是数组的长度.
{
if(k==m-1)//前缀是最后⼀个位置，此时打印排列数.
{
for(int i=0; i<m; i++)
{
printf("%d",list[i]);
}
printf("\n");
return;
}
else
{
//冒泡排序--实现字典序
for(int i = k ; i < m-1; i++)
for(int j = k+1; j < m; j++)
{
if(list[i]> list[j])
Swap(&list[i],&list[j]);
}
for(int i = k; i < m; 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};
c语言如何去学
Perm(a,0,4);
}
总结
  分治法的实现模式可以是递归⽅式，也可以是⾮递归⽅式，⼀般采⽤递归⽅式的算法模式。从算法的⾓度看，分治法得到的⼦问题和原问题是相同的，当然可以⽤相同的函数来解决，区别只在于问题的规模和范围不同。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。