Im looking for an (the) algorithm I believe was published in Quote Quad, probably in the 1980s.
Given a number n, the algorithm calculate the nth permutation of an ordered tuple ie the nth tuple
of all permutation in lexical order.  Ive searched many years of Quote Quad and used Google without
success.  The fact Im most certain of is that it is an APL algorithm.  It wasnt quite a whizzbang
but close; using base convert, rotate, and take/drop.
    Thanks for any help

Hop wrote as below. Here's a Dyalog APL dynamic function nperm
to get the a-th perm of iota w,  as in
      3 nperm 4
0 2 3 1
or

0 1 2 4 3
0 1 3 4 2
0 2 1 4 3
1 3 2 4 0

First you need to express 3 (say) in a representation with 4 3 2 1
as base:
      4 3 2 1 {represent} 3
0 1 1 0
I forget who suggested this trick.  Clearly the numbers 0 1 2 ...
21 22 23 are represented uniquely with this base vector.

Then you need to use this 0 1 1 0 to choose the indices from 0 1 2 3
using the unnamed dynamic function embedded in nperm.

I'm afraid this function is "stack-recursive" but it's still quite
fast for "reasonable" arguments.

It's easy enough to re-express this as a permutation of an ordered
vector v without repetitions,  eg
      v [ 3 nperm {rho} v ]

Function nperm in Weigang transliteration mode:





[5]        np{<-}(1+{reverse}{iota}{omega}){represent}{alpha}
[6]


[9]        {first}{leftbrace}{alpha}{<-}{iota}{rho}{omega}



[13]

[15]           a1,({alpha}~a1){del} 1{drop}{omega}

[17]   {rightbrace}
     {del}

Mike Day
13  7  01

Hop wrote on July 12:

From <http://chilton.com/~jimw/permute.html>:

     {del} Z{<-}J LEXPERM1 N;C;I


[3]    Z{<-},1
[4]    C{<-}1+({reverse}1+{iota}N-1){represent}J
[5]    I{<-}N
[6]   L1:{->}(0=I{<-}I-1)/0
[7]    Z{<-}C[I],Z+Z{>=}C[I]
[8]    {->}L1
     {del}

     {del} Z{<-}J LEXPERM N;C;I


         +} {rho}Z {<-}{->} ({rho}J),N

[4]    Z{<-}(1,{times}/{rho}J){rho}1
[5]    C{<-}1+({reverse}1+{iota}N-1){represent},{transpose}J
[6]    I{<-}N
[7]   L1:{->}(0=I{<-}I-1)/L2
[8]    Z{<-}C[I;]{commabar}Z+Z{>=}({rho}Z){rho}C[I;]
[9]    {->}L1
[10]  L2:Z{<-}{transpose}((1{take}{rho}Z),{reverse}{rho}J){rho}Z
     {del}

1 2 3 4 5 7 6

      P{<-}0 1000 5039 LEXPERM 7
      P

I found Lehmer's algorithm in the paper "Permutation Generation
Methods", by Robert Sedgewick, in _Computing Surveys_, Vol. 9, No. 2,
June 1977.

                                                Jim

Eugene McDonnell asked me to forward his message (below) to the APL
discussion group.  I imagine the references he cites will be useful
to "Hop" who started this thread.

Eugene's function is directly expressible as a Dyalog APL Dynamic
function (using Jim Weigang's transliteration again):

[1]        {gradeup}{gradeup}{alpha},{omega}{rightbrace}
     {del}

      f / 0 1 1 0
 0 2 3 1

Very nice!

Mike Day
14  7  01