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

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

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

/***********************************************/

　　void chang(char str[],int m) /*定义循环左移函数(我没有用左移函数)*/

　　 {

　　 int i,j;

　　 char temp=str[0];

　　 for (i=0;i

　　 str[i]=temp;

　　 }

　　void pai(char str[],int m,int n) /*定义全排列函数*/

　　{

　　 int k;

　　 void chang(char str[],int m);

　　 if (m

　　 {

　　 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

　　void permutation(char a[], int m, int n)

　　{

　　int i;

　　char t;

　　if (m

　　permutation(a, m+1, n);

　　for (i=m+1;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;

　　}