Permutation 
Author Message
 Permutation

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


Tue, 30 Dec 2003 10:01:23 GMT  
 Permutation
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

Quote:


> 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



Wed, 31 Dec 2003 03:11:52 GMT  
 Permutation
Hop wrote on July 12:

Quote:
> Given a number n, the algorithm calculate the nth permutation of an
> ordered tuple ie the nth tuple of all permutation in lexical order.  

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



Wed, 31 Dec 2003 19:23:50 GMT  
 Permutation
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

Quote:

> Mike Day,

> I first saw the 4 3 2 1 radix schems in a function by Luther Woodrum that
> appeared in the APL\360 User's Manual (IBM 1968, p. B.11, function "perm"). I
> later found that this device, called "factorial digits representation" had
> been described by the second-generation University of California at Berkeley
> mathematician D. H. Lehmer (son of ditto D. N. Lehmer) a few years before
> this.

> There is a simpler nonrecursive way to convert from the factorial digits form
> to the standard form, devised by me many years ago, inspired by Luther's
> "perm" function. Permit me to write a function in J:

>      f=: 13 : '/: /: x. , y.'

> Which is "upgrade upgrade x comma y"

>   If you write

>    0 f 1 f 1 f 0
> 0 2 3 1

> Now if one uses J's "insert", which is close to APL's "reduction",

>    f/0 1 1 0
> 0 2 3 1

> I described this and a number of related functions in Vector 12 1, July 1995,
> pp 125-128: "Different Ways of Representing a Permutation".

> I've lost the address of the APL list -- perhaps you'd be good enough to
> forward this to the group.

> Thank you,

> Eugene McDonnell



Thu, 01 Jan 2004 01:21:31 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. all-permutations is faster than permutation

2. A permutation on permutations

3. Generating permutations

4. Finding permutations

5. All Permutations

6. All permutations

7. Permutations

8. Linked list to Permutation vector

9. Permutations

10. Puzzler: function of permutation vector

11. Fwd: re: Puzzler: Permutations and Anagrams

12. Puzzler: Permutations and Anagrams

 

 
Powered by phpBB® Forum Software