c - 我无法找出计算排列的程序中的错误

Question

#include<stdio.h>
#include<conio.h>
main()
{
int i,j,k,x,y,n=4,a[]={1,2,3,4};   //n is the length of the array
for(i=0;i<n;i++)
{
  for(k=0;k<(n-2);k++)
   {
    for(j=(n-1-k);j>=1;j--)
     {
      y=a[j];
      a[j]=a[j-1];
      a[j-1]=y;
      for(x=0;x<n;x++)
        {
         printf("%d",a[x]);
        }
      printf("\t");
     }
   }
}
getch();
}

Answer 1

一些额外的 Material (我有点醉了，明天我可能不得不重新编辑这个，所以请保持谨慎):

Knuth 和 Sedgewick 都在很久以前就研究过排列。

看看:http://www.princeton.edu/~rblee/ELE572Papers/p137-sedgewick.pdf

对于 n 个项目，你有 n!排列，因此对于 13 个项目，您已经有 6 227 020 800 个排列。因此，为大量项目创建所有排列将很快变得不可能。

基本上有两套算法来创建排列，排名/取消排名和增量变化方法。

对于排名/取消排名，您有排名和取消排名两种方法。

Rank 将为您提供排列在生成顺序中的位置。

Unrank 将为您提供位于整数 m 处的排列，其中 0 >= m <= n! 和 n 是您要为其创建排列的项目数量。

这对各种情况都很有用，例如:

创建一个随机排列(您只需创建一个从 0 到 n 的随机数!并调用 unrank(randomNumber))并在位置 randomNumber 处获取排列。

创建序列，获得下一个排列:你有一个排列 p 并调用 Rank(p)，然后调用 Unrank(rank+1)。

增量更改方法:

这些基本上是通过交换来工作的，并且比排名/取消排名更有效:

来自维基百科，无序生成:

 function permutation(k, s) {
     for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j;        // integer division cuts off the remainder
     }
     return s;
 }