Bill Allombert on Fri, 18 Oct 2002 14:04:00 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: numtoperm |
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.