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[2] 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”).

## Spoiler Alert

**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.

• **1987**, *Some Uses of { and }*

```
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.

• **2008**, http://dfns.dyalog.com/n_pmat.htm

```
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]`

:-)