排列问题

1、实现排列A(n,m)

对指定的正整数m,n(约定1<m<=n),具体实现排列A(n,m)。

2、 回溯算法设计

设置一维数组a，a(i)（i=1,2,…,m）在1—n中取值。首先从a(1)=1开始,逐步给a(i)(1≤i≤m)赋值,每一个a(i)赋值从1开始递增至n。

为判断数字是否重复,设置中间变量g：先赋值g=1；若出现某两数字相同(即a(i)=a(j)),则赋值g=0(重复标记)。

若i=m与g=1同时满足,则为一组解,用s统计解的个数后,格式打印输出这组解。

若i<m 且g=1,表明不到m个数字,下一个a(i)从1开始赋值，继续。

若a(i)=n ,则返回前一个数组元素a(i-1)增1赋值。直到a(1)=9时,已无法返回,意味着已全部试毕,求解结束。

3、算法描述

输入正整数n,m,(n≥m);

i=1;a[i]=1;

while (1)

{ g=1;for(j=1;j<i;j++)

  if(a[j]==a[i] ) g=0;    /* 检测,不满足返回 */

  if(g && i==m)

     printf(a[1-m]);       /* 输出一个解 */

  if(i<n && g) {i++;a[i]=1;continue;}

  while(a[i]==n && i>1) i--;   /* 回溯 */

  if(a[i]==n && i==1) break;  /* 退出循环，结束 */

  else a[i]=a[i]+1;

}

4、代码实现

1 #include 
     
       2 #include 
      
        3  4 int main() 5 { 6     int a[100]; 7     int num; 8     int flag; 9     int i,j,k;10     int m,n;11     printf("输入n(A(n,m)):");12     scanf("%d",&n);13     printf("输入m(A(n,m)):");14     scanf("%d",&m);15     i=1;16     a[i]=1;17     num=0;18     while(1)19     {20         flag=1;21         for(k=i-1;k>=1;k--)22         {23             if(a[i]==a[k])24             {25                 flag=0;26             }27         }28         if(flag&&i==m)29         {30             num++;31             for(j=1;j<=m;j++)32             {33                 printf("%d",a[j]);34             }35             printf(" ");36             if(num%6==0)37             {38                 printf("\n");39             }40         }41         if(flag&&i
       
        1)i--;48         if(a[i]==n&&i==1)49         {50             break;51         }52         else53         {54             a[i]++;55         }56     }57     printf("\n排列数A(%d,%d)=%d",n,m,num);58     return 0;59 }
       
      
     

运行结果：

5、扩展

（1）把以上程序中的输出语句printf("%d",a[j])改为printf("%c",a[j]+64);排列(或组合)输出由前n个正整数改变为前n个大写英文字母输出。

运行结果：

（2）把以上程序中的输出语句printf("%d",a[j])改为printf("%c",n+65-a[j]);排列(或组合)输出由前n个正整数改变为前n个大写英文字母逆序输出。

运行结果：