Joerg Arndt on Tue, 09 Oct 2012 07:30:30 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: numtoperm and Factorial Number System |
C(++) code for (various flavors of) numtoperm for permutations (not: multi-permutations) is in the fxt-lib (GPL), see http://www.jjj.de/fxt/ Some description is in the fxtbook, section 10.1, pp.232ff, see http://www.jjj.de/fxt/#fxtbook Lehmer code conversion (from and to factorial numbers) is O(n^2), an n*log(n) routine is given in the fxtbook. For another ordering, there is a O(n) routine, see pp.239ff. We may want to have this as well. @Max: care to send your routines to me? Best regards, jj P.S.: I wonder if other combinatorial routines from the fxt-lib could be used. Of course a build-in pari function for the (direct) generation of all (multiset) permutations (lex order) would be nice, see section 13.2, pp.297ff for the (rather simple) method. (Mixed-radix counting gives multi-subsets and is super-trivial to implement.) Lyndon words, as another random example, are useful to generate all primitive elements of a finite field. Cf. the Sage code in http://oeis.org/A192507 for what I mean. * Max Alekseyev <maxale@gmail.com> [Oct 09. 2012 07:01]: > I'll send the code this week. > As of the current 'default' -- there is no reason to keep it as its > behavior is not documented. > Max > > On Mon, Oct 8, 2012 at 9:52 AM, Charles Greathouse > <charles.greathouse@case.edu> wrote: > > Probably it would be best to allow choosing permutation type with a > > flag, e.g. 0 = default, 1 = lexicographic, 2 = Zakharevich. None of my > > code at present depends on the type but perhaps some does. In any case > > there could be speed implications, especially if the existing code is > > faster (but some applications require lexicographic order). > > > > Charles Greathouse > > Analyst/Programmer > > Case Western Reserve University > > > > On Sun, Oct 7, 2012 at 12:21 PM, Joerg Arndt <arndt@jjj.de> wrote: > >> Please ask Max Alekseyev! > >> IIRC he such code, even for multiset-permutations. > >> > >> While we are at combinatorial generation, > >> are there plans for other types of objects > >> (e.g. partitions, and set partitions)? > >> > >> Best regards, jj > >> > >> > >> * Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> [Oct 07. 2012 18:03]: > >>> * Mathieu Carbou [2012-10-07 01:56]: > >>> [...] > >>> > I was wondering why in PARI the numtoperm does not match the Nth > >>> > permutation in the factorial number system ? > >>> > >>> No particular reason. The code was submitted (by Ilya Zakharevich) and > >>> included essentially "as is". > >>> > >>> > Is there a way to use numtoperm to get the good result or I have to code > >>> > a function which decompose the number in the factorial number system by > >>> > myself ? > >>> > >>> Not currently. There's a long-standing wishlist item in the Bug Tracking System > >>> > >>> http://pari.math.u-bordeaux1.fr/cgi-bin/bugreport.cgi?bug=899 > >>> > >>> asking for a lexicographic ordering (aka Lehmer code). If someone has a > >>> GP or C implementation for this, I have no objection to replacing the > >>> current code. > >>> > >>> [ The current numtoperm / permtonum code should be modified anyway to > >>> return / accomodate t_VECSMALLs: it's more efficient and permutations are > >>> now represented by t_VECSMALLs anyway. This way they can be inverted, > >>> multiplied, etc. ] > >>> > >>> Cheers, > >>> > >>> K.B. > >>> -- > >>> Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 > >>> Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 > >>> 351, cours de la Liberation http://www.math.u-bordeaux1.fr/~belabas/ > >>> F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] > >>> ` > >> > >