# Permutations

I started composing a set of APL exercises in response to a query from a new APL enthusiast who attended Morten’s presentation at Functional Conf, Bangalore, October 2014. The first set of exercise are at a low level of difficulty, followed by another set at an intermediate level. One of the intermediate exercises is:

Permutations

a. Compute all the permutations of `⍳⍵` in lexicographic order. For example:

``````   perm 3
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
``````

b. Write a function that checks whether `⍵` is a solution to `perm ⍺`, without computing `perm ⍺`. You can use the function `assert`. For example:

``````assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕SIGNAL 8 ⋄ shy←0}

pcheck←{
assert 2=⍴⍴⍵:
assert (⍴⍵)≡(!⍺),⍺:
…
1
}

6 pcheck perm 6
1

4 pcheck 2 4⍴0 1 2 3, 0 1 3 2
assertion failure
pcheck assert(⍴⍵)≡(!⍺),⍺:
∧
``````

c. What is the index of permutation `⍵` in `perm ⍺`? Do this without computing all the permutations. For example:

``````   7 ip 1 6 5 2 0 3 4    ⍝ index from permutation
1422
``````

(The left argument in this case is redundant, being the same as `≢⍵`.)

d. What is the `⍵`-th permutation of `⍳⍺`? Do this without computing all the permutations. For example:

``````   7 pi 1442             ⍝ permutation from index
1 6 5 2 0 3 4

(perm 7) ≡ 7 pi⍤0 ⍳!7
1
``````

The Anagram Kata

Coincidentally, Gianfranco Alongi was attempting in APL the anagrams kata from Cyber Dojo:

Write a program to generate all potential anagrams of an input string.

For example, the potential anagrams of “biro” are
```biro bior brio broi boir bori ibro ibor irbo irob iobr iorb rbio rboi ribo riob roib robi obir obri oibr oirb orbi orib```

This is essentially the same program/exercise/kata, because the potential anagrams are `'biro'[perm 4]`. You can compare solutions in other languages to what’s here (google “anagrams kata”).

Deriving a Solution

I am now going to present solutions to part a of the exercise, generating all permutations of `⍳⍵`.

Commonly, in TDD (test-driven development) you start with a very simple case and try to extend it successively to 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”.) 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 entry 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 advancements 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 the shortest known solution, 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

``````    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 and therefore have `⎕io` sprinkled hither, thither, and yon.

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

Written in Dictionary APL, 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 and in a Vector article. The lessons translate directly into Dyalog APL.

``````   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]` :-)​​