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 ⍵. Therefore1+∇ ¯1+⍵ ←→ ∇⍢(¯1∘+)⍵ - Moreover, it is possible to define
≤⍵as⍵-1(decrement) and≥⍵as⍵+1(increment), as in J; whence1+∇ ¯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] :-)
Follow