i can't figure out the bug in my program for calculating permutations

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

Change this:

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

to this:

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

Also, try using more descriptive variable names...

Answer 2

Some additional material (I'm a bit drunk, I will probably have to re-edit this tomorrow, so take it with a grain of salt):

Knuth and Sedgewick both covered permutations aeons ago.

Have a look at: http://www.princeton.edu/~rblee/ELE572Papers/p137-sedgewick.pdf

For n items you have n! permutations, so for 13 items you already have 6 227 020 800 permutations. So creating all permutations for a large set of items will become impossible pretty fast.

There are basically two sets of algorithms to create permutations, ranking/unranking and incremental change methods.

With ranking/unranking you have two methods rank and unrank.

Rank will give you the position of a permutation in the genereration order.

Unrank will give you the permutation that lies at integer m, with 0 >= m <= n! and n the amount of items you want to create permutations for.

This is useful for a variety of cases such as:

Creating a random permutation (you just create a random number from 0 to n! and call unrank(randomNumber)) and get the permutation at position randomNumber.

Creating sequences, getting the next permutation: You have a permutation p and call Rank(p) then Unrank(rank+1).

Incremental change methods:

These basically work through swapping and are more efficient than ranking/unranking:

From wikipedia, unordered generation:

 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 3

I don't know the point of your program, but you may try to read the implementation of std::next_permutation. Generating all permutations with loops is somewhat tricky and I prefer using recursion.