<<   >>

19. Permutations

{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}

Generate the matrix of all permutations of ⍳⍵ in lexicographic order.

Deriving a Solution

Commonly, in TDD (test-driven development) you start with a very simple case and trying to extend it to successively more general cases. It’s all too easy to be led into a dead-end because the simple case may have characteristics absent in a more general case. For myself, for this problem, I would start “in the middle”: Suppose I have perm 3 , obtained by whatever means:

   p
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

How do I get perm 4 from that? One way is as follows:

   p1←0,1+p
   (0 1 2 3[p1]) (1 0 2 3[p1]) (2 0 1 3[p1]) (3 0 1 2[p1])
┌───────┬───────┬───────┬───────┐
│0 1 2 3│1 0 2 3│2 0 1 3│3 0 1 2│
│0 1 3 2│1 0 3 2│2 0 3 1│3 0 2 1│
│0 2 1 3│1 2 0 3│2 1 0 3│3 1 0 2│
│0 2 3 1│1 2 3 0│2 1 3 0│3 1 2 0│
│0 3 1 2│1 3 0 2│2 3 0 1│3 2 0 1│
│0 3 2 1│1 3 2 0│2 3 1 0│3 2 1 0│
└───────┴───────┴───────┴───────┘

So it’s indexing each row of a matrix m by 0,1+p . There are various ways of forming the matrix m , one way is:

   ⍒⍤1 ∘.=⍨ 0 1 2 3
0 1 2 3
1 0 2 3
2 0 1 3
3 0 1 2

(Some authors waxed enthusiastic about this “magical matrix” [69].) In any case, a solution obtains readily from the above description: Form a matrix from the above individual planes; replace the 0 1 2 3 by ⍳⍵ ; and make an appropriate computation for the base case (when 0=⍵). See the 2015-07-12 subsection below.

The Best perm Function

What is the “best” perm function I can write in APL? This “best” is a benchmark not only on my own understanding but also on advances in APL over the years.

“Best” is a subjective and personal measure. Brevity comes into it but is not the only criteria. For example, {(∧/(⍳⍵)∊⍤1⊢t)⌿t←⍉(⍵⍴⍵)⊤⍳⍵*⍵} is short but requires space and time exponential in the size of the result, and that disqualifies it from being “best”. The similarly inefficient {(∧/(⍳⍵)∊⍤1⊢t)⌿t←↑,⍳⍵⍴⍵} is shorter still, but does not work for 1=⍵ .

• 1981, The N Queens Problem [70]

    p←perm n;i;ind;t
   ⍝ all permutations of ⍳n
    p←(×n,n)⍴⎕io
    →(1≥n)⍴0
    t←perm n-1
    p←(0,n)⍴ind←⍳n
    i←n-~⎕io
   l10:p←(i,((i≠ind)/ind)[t]),[⎕io]p
    →(⎕io≤i←i-1)⍴l10

It was the fashion at the time that functions be written to work in either index-origin with ⎕io sprinkled hither, thither, and yon.

• 1987, Some Uses of { and } [49c]

   perm:  ⍪⌿k,⍤¯1 (⍙⍵-1){⍤¯ 1 k~⍤1 0 k←⍳⍵
       :  1≥⍵
       :  (1,⍵)⍴0

Written in Dictionary APL [42], wherein: ⍪⌿⍵ ←→ ⊃⍪⌿⊂⍤¯1⊢⍵ and differs from its definition in Dyalog APL; ⍙ is equivalent to ∇ in dfns; ⍺{⍵ ←→ (⊂⍺)⌷⍵ ; and ¯ by itself is infinity.

• 1990-2007

I worked on perm from time to time in this period, but in J rather than in APL. The results are described in a J essay [71] and in a Vector article [69]. The lessons translate directly into Dyalog APL.

• 2008 [72]

   pmat2←{{,[⍳2]↑(⊂⊂⎕io,1+⍵)⌷¨⍒¨↓∘.=⍨⍳1+1↓⍴⍵}⍣⍵⍉⍪⍬}

In retrospect, the power operator is not the best device to use, because the left operand function needs both the previous result (equivalent to perm ⍵-1) and ⍵ . It is awkward to supply two arguments to that operand function, and the matter is finessed by computing the latter as 1+1↓⍴⍵ .

In this formulation, ⍉⍪⍬ is rather circuitous compared to the equivalent 1 0⍴0 . But the latter would have required a ⊢ or similar device to separate it from the right operand of the power operator.

• 2015-07-12

   perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}

For a time I thought the base case can be ⍳1 0 instead of 1 0⍴0 , and indeed the function works with that as the base case. Unfortunately (⍳1 0)≢1 0⍴0 , having a different prototype and datatype.

• Future

Where might the improvements come from?

  • We are contemplating an under operator whose monadic case is f⍢g ⍵ ←→ g⍣¯1 f g ⍵ . Therefore 1+∇ ¯1+⍵ ←→ ∇⍢(¯1∘+)⍵
  • Moreover, it is possible to define ≤⍵ as ⍵-1 (decrement) and ≥⍵ as ⍵+1 (increment), as in J; whence 1+∇ ¯1+⍵ ←→ ∇⍢≤⍵
  • Monadic = can be defined as in J, =⍵ ←→ (∪⍳⍨⍵)∘.=⍳≢⍵ (self-classify); whence ∘.=⍨⍳⍵ ←→ =⍳⍵

Putting it all together:

   perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,∇⍢≤⍵)⌷⍤1⍒⍤1=⍳⍵}

We should do something about the ,[⍳2] ☺​.​​


Appeared in [73].