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

一些额外的材料（我有点醉了，我明天可能要重新编辑这个，所以把它带上一粒盐）：

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;
 }

Answer 2

改变这个：

for(k=0;k<(n-2);k++)

对此：

for(k=0;k<(n-1);k++)

另外，尝试使用更具描述性的变量名称...

Answer 3

我不知道你的程序的意义，但你可以尝试阅读 std::next_permutation 的实现。使用循环生成所有排列有点棘手，我更喜欢使用递归。