Kth Μετάθεση

[Salvation]

Παιδια καλησπέρα,

 

Προσπαθώ να υλοποιήσω ενα ψευδοκώδικα που βρηκα, ο οποίος παραγει την Κ μετάθεση (lexicographic order). O ψευδοκωδικας ειναι με κληση συναρτησης αναδρομικα:

 

To find permutation x of array A, where A has N elements:

0. if A has one element, return it

1. set p to ( x / (N-1)! ) mod N

2. the desired permutation will be A[p] followed by

permutation ( x mod (N-1)! )

of the elements remaining in A after position p is removed

 

perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}

C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}

perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}

A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}

perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}

D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}

B (because there's only one element)

DB

ADB

CADB

 

Έγραψα ένα κωδικα σε C αλλα δν δουλεύει. Μπορείτε να με βοηθήσετε;

 

>#include <stdio.h>
#include <stdlib.h>
#include <conio.h>


int *perm(int *a,int *b,int number,int index);
int fact(int n);

int main(void)
{
   int *a,num,i,*b;

   printf("Please enter number of cities: ");
   scanf("%d",&num);
   a=(int*)malloc(num*sizeof(int));
   b=(int*)malloc(num*sizeof(int));
   for(i=0;i<num;i++) a[i]=i+1;
   b=perm(a,b,3,0);
   for(i=0;i<num;i++) printf(" %d",b[i]);
   return 0;

}


int *perm(int *a,int *b,int number,int index)
{
   int p,*temp,i,x,length,counter;
   length=sizeof(a)/sizeof(int);
   temp=(int*)malloc((length-1)*sizeof(int));




   if(length!=1)
   {
       p=(number/fact(length-1))%length;
       b[index]=a[p];
       index++;
       counter=0;
       for(i=0;i<length;i++)
       {
           if(i!=p)
           {
               temp[counter]=a[i];
               counter++;

           }

       }
       x=number%fact(length-1);
       b=perm(temp,b,x,index);
       return b;

   }
   else
   {
      b[index]=temp[0];
      return b;


   }

}


int fact(int n)
{
 if (n<=1)
return(1);
 else
n=n*fact(n-1);
return(n);
}

 

Άκυρο παιδια το διόρθωσα!!