lotus

previous page: 100 combinatorics/grid.dissection.p
  
page up: Puzzles FAQ
  
next page: 102 combinatorics/subsets.p

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:













TOP
previous page: 100 combinatorics/grid.dissection.p
  
page up: Puzzles FAQ
  
next page: 102 combinatorics/subsets.p