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

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

I’ve taken to commenting the closing brace of my inner dfns with a home-grown type notation pinched from the Functional Programming community:

```    dref←{                  ⍝ Value for name ⍵ in dictionary ⍺
names values←⍺      ⍝ dictionary pair
(names⍳⊂⍵)⊃values   ⍝ value corresponding to name ⍵
}                       ⍝ :: Value ← Dict ∇ Name
```

I keep changing my mind about whether the result type should be to the left (`Value ← ...`) or to the right (`... → Value`). The FP crowd favours `→ Value` but I’m coming around to `Value ←` because:

* In contrast to (say) Haskell, APL’s function/argument sequences associate right.
* `Value ←` mirrors the result pattern in a tradfn header and so looks familiar.
* The type of function composition `f∘g` is simpler this way round.

Such comments serve as an aide-mémoire when I later come to read the code though, with some ingenuity, the notation might possibly be extended to a more formal system, which could have value to a compiler or code-checker. We would need:

Glyphs for Dyalog’s three primitive atomic data types. For no particularly good reason, I’ve been using:
``` # number ' character . ref ```
Glyphs for a few generic (polymorphic) types. These could be just regular lower-case letters a b c … though I currently prefer greek letters:
``` ⍺ ∊ ⍳ ⍴ ⍵ ... ```

Some constructors for type expressions. This is the most contentious part. For what it’s worth, I’ve been using:
``` ::  is of type ... ∇  function ∇∇  operator ←  returns [⍺] vector of ⍺s {⍺} optional left argument ⍺ ```
For example:
``` foo :: ⍵ ← {⍺} ∇ ⍵ ```
implies:
`foo` is an ambi-valent function whose
– result is of the same type (`⍵`) as its right argument and whose
– optional left argument may be of a different type (`⍺`).

I can abstract/name type expressions with (capitalised) identifiers using `:=`. For example:
``` Dict   := [Name][Value]        ⍝ dictionary name and value vectors Eval   := Expr ← Dict ∇ Expr   ⍝ expression reduction List ⍵ := '∘' | ⍵ (List ⍵)     ⍝ recursive pairs. See ```list``` Name   := ⍞                    ⍝ primitive type: character vector ```
The type: character vector `[']` is used so frequently that the three glyphs fuse into: `⍞`. This means that a vector-of-character-vectors, also a common type, is `[⍞]`.

Primitive and derived function types.
If we’re not too nit-picky and ignore issues such as single extension and rank conformability, we can give at least hints for the types of some primitive functions and operators.

` ⍳ :: # ← ⍺ ∇ ⍺              ⍝ dyadic index-of`
` ⍴ :: ⍺ ← [#] ∇ ⍺            ⍝ reshape (also take, transpose, ...)`

The three forms of primitive composition have interesting types:
``` ∘ :: ⍴ ← {⍺} (⍴ ← {⍺} ∇ ⍳) ∇∇ (⍳ ← ∇ ⍵ ) ⍵     ⍝ {⍺}f∘g ⍵ :: ⍴ ←                 ⍺ ∇∇ (⍴ ← ⍺ ∇ ⍵ ) ⍵   ⍝ A∘g ⍵ :: ⍴ ←      ((⍴ ← ⍺ ∇ ⍵) ∇∇ ⍵ )⍺             ⍝ (f∘B)⍵ ```
It follows that:
``` f :: ⍴ ← {⍺} ∇ ⍳ g :: ⍳ ←     ∇ ⍵ => f∘g :: ⍴ ← {⍺} ∇ ⍵          ⍝ intermediate type ⍳ cancels out ```
and for trains:
``` A :: ⍳                  ⍝ A is an array of type ⍳ f :: ⍳ ← {⍺} ∇ ⍵ g :: ⍴ ← {⍳} ∇ ∊ h :: ∊ ← {⍺} ∇ ⍵ => f g h :: ⍴ ← {⍺} ∇ ⍵        ⍝ fgh fork => A g h :: ⍴ ←     ∇ ⍵        ⍝ Agh fork =>   g h :: ⍴ ← {⍺} ∇ ⍵        ⍝ gh atop ```
For a more substantial example, search function joy for `::` and `:=` in a recent download of dfns.dws.

Muse:
This notation is not yet complete or rigorous enough to be of much use to a compiler but there may already be enough to allow the writing of a dfn, which checks its own and others internal consistency. In the long term, if a notation similar to this evolved into something useful, it might be attractive to allow optional type specification as part of the function definition: without the comment symbol:

```    dref←{                  ⍝ Value for name ⍵ in dictionary ⍺
names values←⍺      ⍝ dictionary pair
(names⍳⊂⍵)⊃values   ⍝ value corresponding to name ⍵
} :: Value ← Dict ∇ Name
```