## enumerating permutations

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

### enumerating permutations

There are 24 = !4 permutations of order (length) 4, and there are 24 unique encodings with base 4 3 2 1:

`      4 - ⍳44 3 2 1      perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2] (⊂0,1+∇ ¯1+⍵) ⌷⍤1 ⍒⍤1 ∘.=⍨ ⍳⍵}          ⍝ from the Dyalog Blog Permutations, 2015-07-20      ⊢ p← perm 4                 ⊢ r← ⍉ (4-⍳4) ⊤ ⍳!40 1 2 3                     0 0 0 0 0 1 3 2                     0 0 1 0 0 2 1 3                     0 1 0 0 0 2 3 1                     0 1 1 0 0 3 1 2                     0 2 0 0 0 3 2 1                     0 2 1 0 1 0 2 3                     1 0 0 0 1 0 3 2                     1 0 1 0 1 2 0 3                     1 1 0 0 1 2 3 0                     1 1 1 0 1 3 0 2                     1 2 0 0 1 3 2 0                     1 2 1 0 2 0 1 3                     2 0 0 0 2 0 3 1                     2 0 1 0 2 1 0 3                     2 1 0 0 2 1 3 0                     2 1 1 0 2 3 0 1                     2 2 0 0 2 3 1 0                     2 2 1 0 3 0 1 2                     3 0 0 0 3 0 2 1                     3 0 1 0 3 1 0 2                     3 1 0 0 3 1 2 0                     3 1 1 0 3 2 0 1                     3 2 0 0 3 2 1 0                     3 2 1 0`

Therefore, there exists a one-to-one and onto (hence invertible) mapping from perm ⍵ to the numbers in base ⍵-⍳⍵, and of course also to ⍳!⍵. These mappings are known in the J world, presented in At Play with J, 1995, by Eugene McDonnell (also in An Implementation of J, 1992 and in a comp.lang.apl post from 1991-04-21). McDonnell called the permutations themselves (p above) as the standard representation; the base ⍵-⍳⍵ numbers (r above) the reduced representation; and the integers ⍳!⍵ the atomic representation. The transformations among the representations, translated from J, are as follows:

`      rfs ← {(⍳≢⍵) (⌷ +.> ↓)¨ ⊂⍵}⍤1    ⍝ reduced  from standard      sfr ← {↑ (⍋∘⍋ ,)/⍵}              ⍝ standard from reduced      sfr 3 1 1 03 1 2 0      rfs 3 1 2 03 1 1 0      p ≡ sfr r1      r ≡ rfs p1      afr ← {(-∘⍳⍨ ⊃⌽⍴⍵) ⊥⍤1 ⊢⍵}       ⍝ atomic  from reduced      rfa ← {(⍺-⍳⍺) ⊤⍤1 0 ⊢⍵}          ⍝ reduced from atomic      afr r0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23      r ≡ 4 rfa afr r1      p ≡ sfr 4 rfa ⍳241      p[i;] ≡ sfr 4 rfa i←?3 4⍴241      afs ← {afr rfs ⍵}                ⍝ atomic from standard      sfa ← {sfr ⍺ rfa ⍵}              ⍝ standard from atomic      afs 2 0 3 113      4 sfa 132 0 3 1      p[13;]2 0 3 1`

(Misalignments in the display are due to defects in the APL Chat Forum software.)

McDonnell derived the rfs and sfr functions in the 1970s, before all the current fancy operator and general array facilities. (I guess this is another example where code was proven correct but not tried [Knuth 1977, page 5].) There is a story that during a visit to the Toronto Islands, McDonnell gave the function definitions to several members of the I.P. Sharp development team ("The Zoo"). When they finally figured out how the functions worked, they burst out laughing.

A note about nomenclature: The function names are of the form rfs (reduced from standard), sfr (standard from reduced), etc. This is preferred (more mnemonic) over the alternatives, rts (reduced to standard), str (standard to reduced), etc. because the argument and result are adjacent to the letters which denote them: standard ← sfr reduced, reduce←rfs standard.

Collected Definitions

`      ⍝perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2] (⊂0,1+∇ ¯1+⍵) ⌷⍤1 ⍒⍤1 ∘.=⍨ ⍳⍵}rfs ← {(⍳≢⍵) (⌷ +.> ↓)¨ ⊂⍵}⍤1    ⍝ reduced  from standardsfr ← {↑ (⍋∘⍋ ,)/⍵}              ⍝ standard from reducedafr ← {(-∘⍳⍨ ⊃⌽⍴⍵) ⊥⍤1 ⊢⍵}       ⍝ atomic   from reducedrfa ← {(⍺-⍳⍺) ⊤⍤1 0 ⊢⍵}          ⍝ reduced  from atomicafs ← {afr rfs ⍵}                ⍝ atomic   from standardsfa ← {sfr ⍺ rfa ⍵}              ⍝ standard from atomic`

See Enumerating Combinations for the enumeration of combinations.
Roger|Dyalog

Posts: 207
Joined: Thu Jul 28, 2011 10:53 am

### Re: enumerating permutations

We extend the permutation enumeration code for large permutations. To motivate a solution, consider the following example:

`      ⎕rl←7*5    ⍝ for reproducible random numbers      ⊢ p←23?233 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2      afs p3.42038E21      (≢p) sfa afs p3 0 21 19 15 9 4 8 12 17 5 20 6 14 1 2 7 10 22 11 13 16 18`

Ideally, the last result should be equal to p. That it does not is due to the fact that a single 64-bit floating point number (the atomic representation) does not have sufficient precision to represent all !23 possible permutations.

To solve the problem, we use the extended precision number facility nats, a monadic operator, from the dfns workspace. The results of nats-derived functions are character vectors of decimal digits; the arguments can be character vectors or scalars or ordinary integers.

`      )copy dfns nats    ⍝ http://dfns.dyalog.com/n_nats.htm      3 +nats 47      (,'7') ≡ 3 +nats 41      3 ×nats 412      '12' ≡ 3 ×nats 41      3 ×nats '4'12      ⊃ ×nats/ 1+⍳5030414093201713378043612608166064768844377641568960512000000000000      !503.04141E64`

Going through the permutation enumeration code:

`      p3 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2      rfs p3 0 19 17 13 7 2 5 7 10 2 10 2 6 2 3 5 4 0 3 2 1 0      p ≡ sfr rfs p1      ⊢a ← afr rfs p3.42038E21      sfr (≢p) rfa a3 0 21 19 15 9 4 8 12 17 5 20 6 14 1 2 7 10 22 11 13 16 18      p3 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2`

sfr and rfs work fine on large permutations. (We leave as exercises for the reader making sfr and rfs work for humongous permutations, permutations where ⌈/p is 2*53 or larger, permutations whose elements require extended precision integers.) afr and rfa require further work; we will develop xfr and rfx, extended (integer) from reduced and reduced from extended.

`      afr{(-∘⍳⍨ ⊃⌽⍴⍵) ⊥⍤1 ⊢⍵}      xfr ← {⊃ ⍵ (+nats).(×nats) ⊖×nats⍀⊖ 1 ↓ 1 ,⍨ -∘⍳⍨ ≢⍵}      xfr rfs p3420381057923137048343`

The main work in xfr is devising an extended precision version of ⊥.

`      rfa{(⍺-⍳⍺) ⊤⍤1 0 ⊢⍵}      rfx ← {(⍺-⍳⍺){0=≢⍺:⍬ ⋄ ((¯1↓⍺)∇ ⍵ ÷nats ⊃⌽⍺), ⍎ (⊃⌽⍺) |nats ⍵}⍵}      ⊢ x← xfr rfs p3420381057923137048343      rfx x      23 rfx x3 0 19 17 13 7 2 5 7 10 2 10 2 6 2 3 5 4 0 3 2 1 0      sfr 23 rfx x3 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2      p3 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2`

Likewise, the main work in rfx is devising an extended precision version of ⊤.

Finally:

`      xfs ← {xfr rfs ⍵}      ⍝ extended from standard      sfx ← {sfr ⍺ rfx ⍵}    ⍝ standard from extended      ⎕rl←7*5      ⊢ q←100?10035 99 21 7 66 54 31 16 57 72 1 78 77 84 40 88 59 17 63 80 67 29 43 82       93 30 91 97 49 38 96 85 73 33 89 9 11 0 70 8 44 19 37 86 94 76 47       95 75 81 25 58 5 34 60 62 98 68 45 28 83 14 36 3 46 50 79 87 26       10 90 92 64 71 32 18 27 55 24 61 51 20 69 6 42 23 65 52 22 56 4       41 12 53 13 2 48 74 39 15      ⊢ x← xfs q335900383154378400660800312803489203857052923167523911203275      847487282020357261413560758006217969893622407667233296160734      92945932950956577271230867064418595657      q ≡ 100 sfx x1      xfact←{⊃ ×nats ⌿ 1+⍳⍵}    ⍝ !⍵      ⊢ x←xfact 1009332621544394415268169923885626670049071596826438162146859296389521759999      3229915608941463976156518286253697920827223758251185210916864      000000000000000000000000      ⊥⍨'0'=x    ⍝ # of trailing 0s in x24      x1← (¯25↓x),'3',24⍴'9'    ⍝ x-1      100 sfx x199 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74       73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50       49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26       25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0      (⊖⍳100) ≡ 100 sfx x11`

Collected Definitions

`      ⍝rfs ← {(⍳≢⍵) (⌷ +.> ↓)¨ ⊂⍵}⍤1    ⍝ reduced  from standardsfr ← {↑ (⍋∘⍋ ,)/⍵}              ⍝ standard from reducedxfr ← {⊃ ⍵ (+nats).(×nats) ⊖×nats⍀⊖ 1 ↓ 1 ,⍨ -∘⍳⍨ ≢⍵}                                 ⍝ extended from reducedrfx ← {(⍺-⍳⍺){0=≢⍺:⍬ ⋄ ((¯1↓⍺)∇ ⍵ ÷nats ⊃⌽⍺), ⍎ (⊃⌽⍺) |nats ⍵}⍵}                                 ⍝ reduced from extendedxfs ← {xfr rfs ⍵}                ⍝ extended from standardsfx ← {sfr ⍺ rfx ⍵}              ⍝ standard from extended`
Roger|Dyalog

Posts: 207
Joined: Thu Jul 28, 2011 10:53 am