Re: numtoperm

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Wed, Oct 16, 2002 at 06:11:45PM +0100, Jon Perry wrote:
> 3.2.33 numtoperm(n; k): generates the k-th permutation (as a row vector of
> length n) of the
> numbers 1 to n. The number k is taken modulo n! , i.e. inverse function of
> permtonum.
> 
> numtoperm(5,0) returns [5,4,3,2,1] which is the k-th permutation of n to 1.
> 
> Also, how is this function defined, as:
> 
> ? alias(np,numtoperm)
> ? np(5,0)
> %3 = [5, 4, 3, 2, 1]
> ? np(5,1)
> %2 = [5, 4, 3, 1, 2]
> ? np(5,2)
> %4 = [5, 4, 2, 3, 1]
> ? np(5,3)
> %5 = [5, 4, 1, 3, 2]
> ? np(5,4)
> %6 = [5, 4, 2, 1, 3]
> ? np(5,5)
> %7 = [5, 4, 1, 2, 3]
> 
> seems erratic. Surely an alphabetic ordering is preferable?

It is slower. You need an extra transposition after the cycle.  I well know
that since I have implemented it in a4galoisgen.  Alphabetic ordering is better
for caching, but is slower for generating the permutation.

Also this function is used in loops like
for(i=1,n!,p=numtoperm(i);...)
or for getting a random permutation:
numtoperm(random(n!))
when the exact order does not matter.
And if it does, could we really break backward compatibility?

If we were to make an iterator that take permutation and return the next one, I
agree it would make more sense to use alphabetic ordering.

> See http://www.users.globalnet.co.uk/~perry/maths/fld/fld.htm for
> inspiration, etc...

yellowpig% wget http://www.users.globalnet.co.uk/~perry/maths/fld/fld.htm
--13:52:25--  http://www.users.globalnet.co.uk:80/%7Eperry/maths/fld/fld.htm
           => `fld.htm'
Connecting to www.users.globalnet.co.uk:80... connected!
HTTP request sent, awaiting response... 404 Not found
13:52:25 ERROR 404: Not found.

Cheers,
Bill.