Compute the nth permutation of k numbers (or objects).

#include <stdio.h>

/*
adapted from 'Notation as a Tool of Thought', by K.E.Iverson

Radix Representation of Permutations
*/

/* direct from radix; of given order */
dfr(short direct[],short radix[],long order)
{
        if (order)
        {
                direct[0] = radix[0];
                dfr (direct+1, radix+1, order-1);
                while (--order)
                        direct[order] += direct[order] >= direct[0];
        }
}
 
/* radix representation; of given order and given index */
rr(short radix[], long order, long index)
{
        int i;
        
        for (i=1; i<=order; i++)
        {
                radix[order-i] = index % i;
                index = index/i;
        }
}
 
show(short perm[],long order)
{
        while(order--)
                printf("%hd ",*perm++);
        printf("\n");
}
 
 
short parity(short radix[],long order)
{
        long p=0;
        
        while(order--)
                p+=*radix++;
        return p%2;
}
 
void usage(char *name)
{
    fprintf(stderr,"usage: %s order number_of_permutation\n",name);
    exit(-1);
}
 
main(int argc, char *argv[])
{
#define MAX_ORDER        512
        short radix[MAX_ORDER], direct[MAX_ORDER];
        long order, nth;
        
        if (argc!=3) usage(argv[0]);
        order = atol(argv[1]);
        nth = atol(argv[2]);
        rr(radix, order, nth-1);        /* where 0 is the first permuatation */
        dfr(direct, radix, order);
        
        printf("radix  "); show(radix,order);
        printf("direct "); show(direct,order);
        printf("parity %d\n",parity(radix,order));
}
 
 
-- 
J. Henri Schueler, H&h Software, Toronto        +1 416 698 9075 
jhs@ipsa.reuter.com