关于全排列算法,大家请指导!

核心提示：关于全排列算法,大家请指导!我不知道大家有没有听说,明年起程序员考试就不分初,中,高级了,而我们软件专业明年就要过程序了,据说相当于考中程,或者还要难一些,虽然不知道消息的正确性,但这的确是我们的老师告诉我们的,所以老师就出一些题给我们练,下面是一道关于数学中全排列的算法的问题,编了我4天!真是的看起来轻易,编起来难.

关于全排列算法,大家请指导! 我不知道大家有没有听说,明年起程序员考试就不分初,中,高级了,而我们软件专业明年就要过程序了,据说相当于考中程,或者还要难一些,虽然不知道消息的正确性,但这的确是我们的老师告诉我们的,所以老师就出一些题给我们练,下面是一道关于数学中全排列的算法的问题,编了我4天!真是的看起来轻易,编起来难..........下面给出我的源代码,并给大家解释我的思路: /***********************************************/
void chang(char str[],int m)  /*定义循环左移函数(我没有用左移函数)*/
 {
  int i,j;
  char temp=str[0];
  for (i=0;i<m;i++) str[i]=str[i+1];
  str[i]=temp;
 }
void pai(char str[],int m,int n) /*定义全排列函数*/
{
 int k;
 void chang(char str[],int m);
 if (m<n)　　　  /* 定 义 递 归 调 用 出 口  */
  {
　 for (k=0;k<=m;k++)
　  {
　　 pai(str,m+1,n); /*递归调用*/
　　 chang(str,m); /*调用左移函数*/
　  }
  }
 else PRintf("%s ",str);
}
#include "stdio.h"
main()
{char str[]="ABCD"; /*全排列字符,可以任意多个(相应的下面排列函数中参数"4"改成全排列字符的个数)*/
clrscr();
pai(str,0,4); /*这里参数0(下标)表示从第一个元素开始,4表示元素个数(不是下标)*/
getch();
}
/*********************************************/ 下面我来解释一下,我花了近1天的时间,找到这样一个规律如下:
　　　　　　　　　　　　　 ┏ ABCD
　　　　　　　　　　　　　 ┣ BCDA
　　　　　　　　 ┏ ABCD ━┫
　　　　　　　　 ┃　　　  ┣ CDAB
　　　 ┏ ABCD ━╋ BCAD　 ┗ DABC
　　　 ┃　　　  ┃　　　　 .
　　　 ┃　　　  ┗ CABD　  .
ABCD ━┫　　　　　　　　　 .　　　　　　　 
　　　 ┃　　　  ┏ BACD　  .
　　　 ┃　　　  ┃　　　　 .
　　　 ┗ BACD ━╋ ACBD　 ┏ CBAD
　　　　　　　　 ┃　　　  ┣ BADC
　　　　　　　　 ┗ CBAD ━┫
　　　　　　　　　　　　　 ┣ ADCB
　　　　　　　　　　　　　 ┗ DCBA
简化图如下所示 ==>
　　　　　　　　　　 ┏ ABCD
　　　　　　　　　　 ┣ BCDA
　　　　　  ┏ ABC ━┫
　　　　　  ┃　　　 ┣ CDAB
　  ┏ AB ━╋ BCA　 ┗ DABC
　  ┃　　  ┃　　　  .
　  ┃　　  ┗ CAB　  .
A ━┫　　　　　　　  .　　　　　　　 
　  ┃　　  ┏ BAC　  .
　  ┃　　  ┃　　　  .
　  ┗ BA ━╋ ACB　 ┏ CBAD
　　　　　  ┃　　　 ┣ BADC
　　　　　  ┗ CBA ━┫
　　　　　　　　　　 ┣ ADCB
　　　　　　　　　　 ┗ DCBA
大家看到了,以上就是一步一步循环左移就能得到所有全排列的数了.以上程序在Trubo C 2.0 中运行通过,假如大家还有什么疑问,请加我QQ:156301529,Email:rodgersnow@163.com,我们共同讨论.另外,我在想,假如是n个数或字符中取m个进行排列的话,该怎么改呢?目前正在考虑中,本人觉得难度很大,希望大家能帮帮我,请加我QQ,谢谢!
另附我在网上找到的经典全排列算法,叫"后补法",大家自己好好研究吧,在Trubo C 2.0 中运行通过了的.
#include <stdio.h>
void permutation(char a[], int m, int n)
{
int i;
char t;
if (m<n-1) {
permutation(a, m+1, n);
for (i=m+1;i<n;i++) {
t=a[m]; a[m]=a[i]; a[i]=t;
permutation(a, m+1, n); t=a[m]; a[m]=a[i]; a[i]=t;
}
} else
{
 printf("%s ", a);
}
}
int main() {
char a[]="ABCDE";
permutation(a, 0,5);
return 0;
}