enumerating permutations

[Roger|Dyalog]

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

      4 - ⍳4
4 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) ⊤ ⍳!4
0 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 0
3 1 2 0
      rfs 3 1 2 0
3 1 1 0

      p ≡ sfr r
1
      r ≡ rfs p
1

      afr ← {(-∘⍳⍨ ⊃⌽⍴⍵) ⊥⍤1 ⊢⍵}       ⍝ atomic  from reduced
      rfa ← {(⍺-⍳⍺) ⊤⍤1 0 ⊢⍵}          ⍝ reduced from atomic

      afr r
0 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 r
1
      p ≡ sfr 4 rfa ⍳24
1
      p[i;] ≡ sfr 4 rfa i←?3 4⍴24
1

      afs ← {afr rfs ⍵}                ⍝ atomic from standard
      sfa ← {sfr ⍺ rfa ⍵}              ⍝ standard from atomic

      afs 2 0 3 1
13
      4 sfa 13
2 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 standard
sfr ← {↑ (⍋∘⍋ ,)/⍵}              ⍝ standard from reduced

afr ← {(-∘⍳⍨ ⊃⌽⍴⍵) ⊥⍤1 ⊢⍵}       ⍝ atomic   from reduced
rfa ← {(⍺-⍳⍺) ⊤⍤1 0 ⊢⍵}          ⍝ reduced  from atomic

afs ← {afr rfs ⍵}                ⍝ atomic   from standard
sfa ← {sfr ⍺ rfa ⍵}              ⍝ standard from atomic

See Enumerating Combinations for the enumeration of combinations.

[Roger|Dyalog]

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?23
3 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2

      afs p
3.42038E21
      (≢p) sfa afs p
3 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 4
7
      (,'7') ≡ 3 +nats 4
1
      3 ×nats 4
12
      '12' ≡ 3 ×nats 4
1
      3 ×nats '4'
12

      ⊃ ×nats/ 1+⍳50
30414093201713378043612608166064768844377641568960512000000000000
      !50
3.04141E64

Going through the permutation enumeration code:

      p
3 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2
      rfs p
3 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 p
1

      ⊢a ← afr rfs p
3.42038E21
      sfr (≢p) rfa a
3 0 21 19 15 9 4 8 12 17 5 20 6 14 1 2 7 10 22 11 13 16 18
      p
3 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 p
3420381057923137048343

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

      rfa
{(⍺-⍳⍺) ⊤⍤1 0 ⊢⍵}

      rfx ← {(⍺-⍳⍺){0=≢⍺:⍬ ⋄ ((¯1↓⍺)∇ ⍵ ÷nats ⊃⌽⍺), ⍎ (⊃⌽⍺) |nats ⍵}⍵}
      ⊢ x← xfr rfs p
3420381057923137048343

      rfx x
      23 rfx x
3 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 x
3 0 21 19 15 9 4 8 12 17 5 20 6 14 7 11 18 16 1 22 13 10 2
      p
3 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?100
35 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 q
335900383154378400660800312803489203857052923167523911203275
      847487282020357261413560758006217969893622407667233296160734
      92945932950956577271230867064418595657

      q ≡ 100 sfx x
1

      xfact←{⊃ ×nats ⌿ 1+⍳⍵}    ⍝ !⍵
      ⊢ x←xfact 100
9332621544394415268169923885626670049071596826438162146859296389521759999
      3229915608941463976156518286253697920827223758251185210916864
      000000000000000000000000
      ⊥⍨'0'=x    ⍝ # of trailing 0s in x
24
      x1← (¯25↓x),'3',24⍴'9'    ⍝ x-1
      100 sfx x1
99 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 x1
1

Collected Definitions

      ⍝
rfs ← {(⍳≢⍵) (⌷ +.> ↓)¨ ⊂⍵}⍤1    ⍝ reduced  from standard
sfr ← {↑ (⍋∘⍋ ,)/⍵}              ⍝ standard from reduced

xfr ← {⊃ ⍵ (+nats).(×nats) ⊖×nats⍀⊖ 1 ↓ 1 ,⍨ -∘⍳⍨ ≢⍵}
                                 ⍝ extended from reduced
rfx ← {(⍺-⍳⍺){0=≢⍺:⍬ ⋄ ((¯1↓⍺)∇ ⍵ ÷nats ⊃⌽⍺), ⍎ (⊃⌽⍺) |nats ⍵}⍵}
                                 ⍝ reduced from extended

xfs ← {xfr rfs ⍵}                ⍝ extended from standard
sfx ← {sfr ⍺ rfx ⍵}              ⍝ standard from extended