Utility Corner: Permutations and Anagrams
Vector 21:2, page 27
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 27
Utility Corner: Permutations and Anagrams¶
(The purpose of this column is to make you more productive by introducing you to utility functions. Think of utility functions as APL functions that have names instead of symbols. By expanding your function vocabulary, you’ll be able to write APL code that’s more concise, more efficient, and more readable.)
In last issue’s Limbering Up column, you were asked to define a monadic utility function PERMUTE, whose argument is a positive integer N and whose result is an N-column, (!N)-row matrix, in which each row is a different permutation of ⍳N.
Your second task was to write a monadic function ANAGRAM, whose argument is a character vector, and whose result is a character matrix in which each row is a different arrangement of the argument’s letters. (ANAGRAM calls PERMUTE.)
The ANAGRAM function is fairly straightforward:
∇ R←ANAGRAM WORD
[1] ⍝ Returns all different combinations
[2] ⍝ of the characters in vector WORD.
[3] ⍝ Needs PERMUTE
[4] ⍝
[5] ⍝ Sort chars to check for duplicates
[6] ⍝ and to have result sorted if none:
[7] WORD←WORD[⎕AV⍋WORD]
[8] ⍝ All permutations:
[9] R←WORD[PERMUTE⍴WORD]
[10] ⍝ Exit if no duplicate chars
[11] →(∧/WORD≠1⌽WORD)/0
[12] R←R[⎕AV⍋R;] ⍝ Sort permutations
[13] ⍝ Eliminate duplicates
[14] R←(¯1↓1,∨/R≠1⊖R)⌿R
∇
There were two common mistakes made within ANAGRAM functions submitted. The first was to forget to eliminate the duplicate permutations caused by redundant letters. For example, the permutations 'SMSI'[2 4 1 3] and 'SMSI'[2 4 3 1] both return the string MISS.
The second mistake was to assume you can avoid sorting the character matrix (to catch duplicates) by first sorting the character string. The assumption seems reasonable but isn’t. For example, the sorted permutations 'IMSS'[1 3 2 4], 'IMSS'[1 3 4 2] and 'IMSS'[1 4 2 3] return the unsorted strings ISMS, ISSM, ISMS.
The PERMUTE functions submitted seemed to fall into three categories: those that used recursion (PERMUTE calls itself), those that used looping, and those that boldly solved the problem without recursion or looping.
Let’s address the bold solutions first. George Brigham’s solution appeared in the May 1995 issue of the Big APL Newsletter (published by the New York chapter of SIGAPL: NY/SIGAPL, P.O. Box 2697, New York, NY 10163-2697).
∇ R←PERMUTE N
[1] ⍝ Returns an N-column matrix, in
[2] ⍝ which each row is a different
[3] ⍝ permutation of ⍳N. Has !N rows.
[4] ⍝
[5] R←(N/N)⊤(⍳N*N)-⎕IO
[6] R←⎕IO+⍉(∧⌿∨/[1+⎕IO]((⍳N)-⎕IO)∘.=R)/R
∇
In this solution, encode (⊤) is used to generate all possible combinations of the numbers in ⍳N (in origin 0), even duplicates. For example, for N=3,
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
Those columns that contain exactly one each of the numbers 0 1 2 are selected, the result is transposed, and the numbers are adjusted back to origin 1 if needed.
In the June 1995 issue of Big APL, J. Philip Benkard presented a variation on the theme:
∇ R←PERMUTE N
[1] ⍝ Returns an N-column matrix, in
[2] ⍝ which each row is a different
[3] ⍝ permutation of ⍳N. Has !N rows.
[4] ⍝
[5] R←(N/N)⊤(⍳N*N)-⎕IO
[6] R←⎕IO+⍉((N+.*(⍳N)-⎕IO)=N+.*R)/R
∇
The numbers in the matrix are applied as exponents of N, and are added across the rows. The result for each column, say (3*0)+(3*0)+(3*1), is then compared to the sum on N raised to each of the powers in ⍳N (in origin 0), say (3*0)+(3*1)+(3*2). Only those columns with exactly one each of the numbers 0 1 2 will match the total and be selected.
In the category of recursive solutions is this function, the heart of which came from John Sullivan:
∇ R←X PERMUTE N;Y
[1] ⍝ Returns an N-column matrix, in
[2] ⍝ which each row is a different
[3] ⍝ permutation of ⍳N. Has !N rows.
[4] ⍝ Left argument is used when called
[5] ⍝ recusively (if N≥4).
[6] ⍝
[7] ⍝ For N∊0 1 2 3, results hard-coded:
[8] →(N=0 1 2 3)/L0,L1,L2,L3
[9] Y←⍳N
[10] R←⊃,[⎕IO]/Y,¨((⊂Y)~¨Y)PERMUTE¨N-1
[11] →L4
[12] L0:R←1 0⍴⍳0
[13] →L4
[14] L1:R←1 1⍴⍳1
[15] →L4
[16] L2:R←2 2⍴⎕IO+0 1 1 0
[17] →L4
[18] L3:R←6 3⍴⎕IO+0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
[19] ⍝
[20] ⍝ Exit if no left argument
[21] L4:→(0=⎕NC'X')/0
[22] R←X[R] ⍝ Map result into left arg
∇
Because recursive solutions tend to call themselves at one less level of complexity (in this instance via PERMUTE N-1), any method that speeds up the lower levels will speed up the overall recursive process. In this case, PERMUTE checks whether its right argument is 0, 1, 2, or 3, and returns the permutation matrix directly without recursing further (lines [12], [14], [16], [18]).
The core algorithm of PERMUTE (line [10]) recognizes the fact that each higher level permutation is a function of the permutation below it. For example, here’s the result of PERMUTE 4 (truncated, and with extra spacing):
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2 1,(2 3 4)[PERMUTE 3]
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1 2,(1 3 4)[PERMUTE 3]
2 4 1 3
2 4 3 1
(etc.)
The actual indexing does not occur on line [10]. Instead, on that line, PERMUTE is given an optional left argument (e.g. 1 3 4) that is indexed on line [22].
John’s PERMUTE function requires an APL implementation that supports nested arrays. The next recursive function, form Ram Biyani, takes a similar tack, but avoids the use of nested arrays.
∇ R←PERMUTE N;A;I;J;M;P;S;Y
[1] ⍝ Returns an N-column matrix, in
[2] ⍝ which each row is a different
[3] ⍝ permutation of ⍳N. Has !N rows.
[4] ⍝ Recursive if N≥4
[5] ⍝
[6] ⍝ For N∊0 1 2 3, results hard-coded:
[7] →(N=0 1 2 3)/L0,L1,L2,L3
[8] M←1↑⍴J←PERMUTE P←N-1 ⍝ Do a prev one
[9] S←N×N
[10] Y←⍳N
[11] ⍝ Rows of ⍳N each with one different
[12] ⍝ element moved to the front of row:
[13] A←Y,(N,P)⍴(S⍴0,N⍴1)/S⍴Y
[14] ⍝ Pluck col-wise with permutations:
[15] R←((N×M),N)⍴A[;⎕IO,1+J]
[16] →0
[17] L0:R←1 0⍴⍳0
[18] →0
[19] L1:R←1 1⍴⍳1
[20] →0
[21] L2:R←2 2⍴⎕IO+0 1 1 0
[22] →0
[23] L3:R←6 3⍴⎕IO+0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
∇
One immediate advantage of this function over the previous one is that it makes just one recursive call at each level. For example, when doing PERMUTE 4, the execution of PERMUTE 3 occurs just once (on line [8]). In the previous function, PERMUTE 3 is called four times (via the each ¨ operator).
The core algorithm of this function is located on lines [13] and [15]. The expression on line [13] returns a matrix in this form (for PERMUTE 4, shown with extra spacing):
To get the required permutations, you need to compute all permutations of the last three columns of each row. For example:
This is done for all rows at once via column-indexing on line [15].
In the category of looping solutions is the following submission, which was developed as a group effort by members of the ‘comp.lang.apl’ group on the Internet. Among the contributors were Jim Weigang, Roger Hui, and others.
∇ R←PERMUTE N;A;I
[1] ⍝ Returns an N-column matrix, in
[2] ⍝ which each row is a different
[3] ⍝ permutation of ⍳N. Has !N rows.
[4] ⍝
[5] R←1 0⍴I←0
[6] L1:→(N<I←I+1)/L2
[7] A←+⍀(⍳I),[⎕IO]1,(I-1 1)⍴I↑¯1
[8] R←A[;⎕IO,1+R]
[9] →L1
[10] L2:R←((!N),N)⍴R
∇
The heart of this algorithm is on lines [7] and [8], and is in fact the same algorithm used in the previous PERMUTE function. The matrix A computed on line [7] (say for I=4) is the same as the matrix A computed on line [13] of the previous function (for N=4).
One subtle difference between these two functions is the timing of the reshape operation on the result of the column-indexing. Reshaping is needed to convert from shape (N,(!N-1),N) to shape ((!N),N). In the former function, reshaping is done immediately after indexing so the shape of the recursive call will be correct. In the latter function, reshaping is postponed until the end of the loop (on line [10]). By the time the reshape takes place, the shape of R is (N,(N-1),(N-2),(N-3),...,1,1,N).
We did some timings to see which of these PERMUTE functions is fastest. Here are the results:
| N=4 | N=5 | N=6 | N=7 | |
|---|---|---|---|---|
| No Loop 1 | 6.77 | 90.00 | 1601.82 | Huge |
| No Loop 2 | 7.64 | 98.96 | 1648.18 | Huge |
| Recurse 1 | 2.64 | 14.77 | 93.82 | 686.36 |
| Recurse 2 | 1.00 | 2.27 | 6.05 | 31.18 |
| Looping | 1.73 | 2.64 | 6.05 | 30.55 |
The times have been scaled so they are all relative to the fastest time. For example, Recurse 1 takes 2.64 times as long to run for N-4 as does Recurse 2 for N=4; and Looping takes 30.55 time as long to run for N=7 as Recurse 2 does for N=4.
The two non-looping functions are painfully slow. Boldness doesn’t necessarily translated to quickness. Too many comparisons and calculations are being made, especially as N gets larger.
The first recursive function is much better than the non-looping functions but gets unwieldy as N get large because of its need to call itself !N-1 times (though one-sixth [!3] of these calls are avoided due to the special case logic used when N is 3 or less). The last two functions, for practical purposes, are equally efficient. That’s no surprise since they use the same approach. Once again, we see that recursing is just looping in sheep’s clothing.
Limbering Up: Market Days¶
(The purpose of this column is to work some flab off your APL midsection. Like muscles, your APL skills can atrophy if not exercised with adequate frequency and variety. This column presents a task for you to perform. Set aside a few minutes from your busy schedule and work the task. Mail in your solution and stay tuned for the results.)
When working with investment data, a special calendar must be used – the calendar that has one day per “Market Day,” i.e. per day that the securities market is open for trading. The market is not open at weekends nor on certain holidays. For certain analyses, it is necessary to move forward or backward a certain number of market days. How is this done?
Suppose the “Market Day” calendar is expressed in two arrays, ciy and cid:
ciy
1994 1995
⍴cid
2 12 31
cid
WWDDDDDWWDDDDDWWDDDDDWWDDDDDWWD
DDDDWWDDDDDWWDDDDDWWHDDDDWWDXXX
DDDDWWDDDDDWWDDDDDWWDDDDDWWDDDD
HWWDDDDDWWDDDDDWWDDDDDWWDDHDDWX
WDDDDDWWDDDDDWWDDDDDWWDDDDDWWHD
DDDWWDDDDDWWDDDDDWWDDDDDWWDDDDX
DWWHDDDDWWDDDDDWWDDDDDWWDDDDDWW
DDDDDWWDDDDDWWDDDDDWWDDDDDWWDDD
DDWWHDDDDWWDDDDDWWDDDDDWWDDDDDX
WWDDDDDWWDDDDDWWDDDDDWWDDDDDWWD
DDDDWWDDDDDWWDDDDDWWDDDHDWWDDDX
DDWWDDDDDWWDDDDDWWDDDDDWWHDDDDW
WHDDDDWWDDDDDWWDDDDDWWDDDDDWWDD
DDDWWDDDDDWWDDDDDWWHDDDDWWDDXXX
DDDWWDDDDDWWDDDDDWWDDDDDWWDDDDD
WWDDDDDWWDDDDHWWDDDDDWWDDDDDWWX
DDDDDWWDDDDDWWDDDDDWWDDDDDWWHDD
DDWWDDDDDWWDDDDDWWDDDDDWWDDDDDX
WWDHDDDWWDDDDDWWDDDDDWWDDDDDWWD
DDDDWWDDDDDWWDDDDDWWDDDDDWWDDDD
DWWHDDDDWWDDDDDWWDDDDDWWDDDDDWX
WDDDDDWWDDDDDWWDDDDDWWDDDDDWWDD
DDDWWDDDDDWWDDDDDWWDDDHDWWDDDDX
DWWDDDDDWWDDDDDWWDDDDDWWHDDDDWW
ciy is a vector of the years in the calendar. cid is a 3-dimensional character array with one plane per year in ciy, 12 rows (one per month), and 31 columns (one per day). Thus, the ninth row of the second plane corresponds to September 1995:
The Ds correspond to market days, the Ws to weekend days, the Hs to holidays, and the Xs to non-existent days. For example, September 4 is a holiday (Labor Day); September 2 and 3 are weekend days; and September 31 does not exist.
Your task is to write a monadic function DAYSPLUS whose left argument is an array of (market day) dates and whose right argument is a corresponding array of numbers of days to add. The result is an array of the (market day) dates that come from the date “addition.” For example,
The arguments should be scalar conformable, you know, vector and vector returns vector, matrix and scalar returns matrix, and so on. Assume globals ciy and cid.
Send your solution to:
Vector Production, Brook House, Gilling East, York YO62 4JJ, UK
email: apl385@compuserve.com
The notable functions and their authors’ names will be printed in the next issue of Vector. Good luck and happy limbering.
Reprinted with kind permission from Zark APL Tutor News, a quarterly publication of Zark Incorporated, 23 Ketchbrook Lane, Ellington, CT06029, USA