101 combinatorics/permutation.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
101 combinatorics/permutation.p
Compute the nth permutation of k numbers (or objects).
combinatorics/permutation.s
#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
Continue to:
My Books
