Re: numtoperm and Factorial Number System

[Joerg Arndt <arndt@jjj.de>]

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]
> >>> `
> >>
> >