Puzzler: Permutations and Anagrams
Author Message Puzzler: Permutations and Anagrams

The November 1995 issue of Dr. Dobbs has an article by Mani Iyer
entitled "Permutation Generation Using Matrices" (p. 133).
Unfortunately, the algorithm described in the article doesn't actually
work.  I mentioned this to Mani and he sent me a corrected version.  The
algorithm is not as fast (in APL, at least) as the algorithms described
here in June, and the result isn't in sorted order, and it doesn't work
for N{<=}2.  But the technique is intriguing because it builds a set of
square matrices and extracts permutations by reading off the rows and
columns of the matrices.  Half the permutations are found in the rows
and half in the columns!  An APL implementation is appended below.

The article has a pointer to an interesting paper: "Permutation
Generation Methods", by Robert Sedgewick, in _Computing Surveys_, Vol.
9, No. 2, June 1977.  (Incidentally, Roger Hui's indexing algorithm is
not among those listed.)  The paper describes an algorithm, attributed
to D. N. Lehmer, for generating the i-th lexical pemutation of {iota}N
(function LEXPERM, below).  I had wondered how J's "atomic permutation"
function was able to generate the i-th lexical permutation so quickly.
It's simple enough to invert the algorithm to produce a function similar
to J's "atomic index" function (PERMNDX below).

Jim

Note:  These programs assume #IO is 1.
For you IBMers, {commabar} is ,[#IO].

{del} Z{<-}PERMDD3 N;I;S

+}{iota}{omega}

    Z{<-}1 2{rho}{iota}2
    I{<-}2
   L1:{->}(N<I{<-}I+1)/L2
    Z{<-}I{slashbar}Z,I
    Z{<-}((1{take}{rho}Z){rho}-{iota}I){rotate}Z
   {->}L1
  L2:S{<-}((1{take}{rho}Z){divide}N),N,N
   Z{<-}Z{commabar}({rho}Z){rho}1 3 2{transpose}S{rho}Z

{del}

LEXPERM1 and PERMNDX1 are simple versions that process only a single
permutation.  LEXPERM and PERMNDX are more complicated parallel versions
that accept or return an array of permutation indices.  Some examples:

1 2 3 4 5 7 6

P{<-}0 1000 5039 LEXPERM 7
P

PERMNDX P
0 1000 5039

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

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

{del} Z{<-}PERMNDX1 P;N

    N{<-}{rho}P{<-},P
    Z{<-}{iota}0
   L1:{->}(1{>=}{rho}P)/L2
    Z{<-}Z,1{take}P
    P{<-}1{drop}P-P>1{take}P
    {->}L1
   L2:Z{<-}({reverse}1+{iota}N-1){basevalue}Z-1
{del}

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

+}{rho}J),N

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

{del} Z{<-}PERMNDX P;S

    S{<-}{rho}P
    P{<-}{transpose}(({times}/{neg}1{drop}S),{neg}1{take}1,S){rho}P
    Z{<-}(0 1{times}{rho}P){rho}0
   L1:{->}(1{>=}1{take}{rho}P)/L2
    Z{<-}Z{commabar}P[1;]
   P{<-}1 0{drop}P-P>({rho}P){rho}P[1;]
   {->}L1
  L2:Z{<-}({neg}1{drop}S){rho}({reverse}1+{iota}{neg}1+{neg}1{take}1,S){+
+}{basevalue}Z-1
{del}

Sat, 23 May 1998 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages