
Chapter 16: RearrangementsThis chapter covers rearranging the items of arrays: permuting, sorting, transposing, reversing, rotating and shifting. 16.1 PermutationsA permutation of a vector is another vector which has all the items of the first but not necessarily in the same order. For example, z is a permutation of y where:
The index vector 4 2 3 1 0 is itself a permutation of the indices 0 1 2 3 4, that is, i. 5, and hence is said to be a permutation vector of order 5. Notice the effect of this permutation: the first and last items are interchanged and the middle three rotate position amongst themselves. Hence this permutation can be described as a combination of cycling two items and cycling three items. After 6 (= 2 * 3) applications of this permutation we return to the original vector. p =: 4 2 3 1 0 & {
The permutation 4 2 3 1 0 can be represented as a cycle of 2 and a cycle of 3. The verb to compute this cyclic representation is monadic C. . C. 4 2 3 1 0 +++ 3 1 24 0 +++ Thus we have two representations of a permutation: (4 2 3 1 0) is called a direct representation and (3 1 2 ; 4 0) is called a cyclic representation. Monadic C. can accept either form and will produce the other form:
The dyadic verb C. can accept either form as its left argument, and permutes its right argument.
16.1.1 Abbreviated PermutationsDyadic C. can accept a left argument which is an abbreviation for a (direct) permutation vector. The effect is to move specified items to the tail, one at a time, in the order given.
With the abbreviated form, successive items are taken from the original vector: notice how the following two examples give different results.
If the left argument is boxed, then each box in turn is applied as a cycle:
If a is an abbreviated permutation vector (of order n) then the fulllength equivalent of a is given by (a U n) where U is the utility function: U =: 4 : 0 z =: y.  x. ((i. y.) . z), z ) For example, suppose the abbreviated permutation a is (1 3) then we see:
16.1.2 Inverse PermutationIf f is a fulllength permutation vector, then the inverse permutation is given by (/: f). (We will look at the verb /: in the next section.)
16.1.3 Atomic Representations of Permutations.If y is a vector of length n, then there are altogether ! n different permutations of y. A table of all permutations of order n can be generated by the expression (tap n) where tap is a utility verb defined by: tap =: i. @ ! A. i. tap 3 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0 It can be seen that these permutations are in a welldefined order, and so any permutation of order n can be identified simply by its index in the table (tap n). This index is called the atomic representation of the permutation. The monadic verb A. computes the atomic representation. For example, given an order3 permutation, e.g. 2 1 0, then A. 2 1 0 yields the index in the table (tap 3).
Notice that A. gives its result as an extended integer (5x) rather than simply 5. (Extended integers will be covered in Chapter 19.) The reason is that since the table (tap n) is of length !n, that is, potentially very long, indexes into it may need to be very long numbers. The dyadic verb A. applies an atomic representation of a permutation.
Here is an example of the use of A.. The process of running through all the permutations of something (say to search for anagrams of a word) might take a very long time. Hence it might be desirable to run through them say 100 at a time. Here is a verb which finds a limited number of permutations. The argument is a boxed list: a vector to be permuted, followed by a starting permutationnumber (that is, atomic index) followed by a count of the permutions to be found. LPerms =: 3 : 0 'arg start count' =. y. (start + i. count) A. " 0 1 arg )
16.2 SortingThere is a builtin monad, /: (slash colon, called "Grade Up"). For a list L, the expression (/: L) gives a set of indices into L, and these indices are a permutationvector.
These indices select the items of L in ascending order. That is, the expression ((/: L) { L) yields the items of L in order.
For sorting into descending order, the monad \:(backslash colon, called "Grade Down") can be used.
Since L is a character list, its items are sorted into alphabetical order. Numeric lists or boxed lists are sorted appropriately.
Now consider sorting the rows of a table. Here is an example of a table with 3 rows: T =: (". ;. _2) 0 : 0 'WA' ;'Mozart'; 1756 'JS' ;'Bach' ; 1685 'CPE';'Bach' ; 1714 ) Suppose we aim to sort the rows of the table into order of dateofbirth shown in column 2 (the third column). We say that column 2 contains the keys on which the table is to be sorted. We extract the keys with the verb 2&{"1, generate the permutation vector with /: applied to the keys, and then permute the table.
The dyadic case of /: allows the expression (/: keys { T) to be abbreviated as (T /: keys).
Suppose now we need to sort on two columns, say by last name, and then by initials. The keys are column 1 then column 0.
These examples show that the keys can be a table, and the /: verb yields the permutationvector which puts the rows of the table into order. In such a case, the first column of the table is the most significant, then the second column, and so on. 16.2.1 Predefined Collating SequencesCharacters are sorted into "alphabetical order", numbers into "numerical order" and boxes into a welldefined order. The order for sorting all possible keys of a given type is called a collating sequence (for keys of that type). We have three predefined collating sequences. The collating sequence for characters is the ASCII character set. The builtin J noun a. gives the value of all 256 characters in "alphabetical" order. Note that uppercase letters come before lowercase letters. 65 66 67 97 98 99 { a. ABCabc With numerical arguments, complex numbers are ordered by the real part then the imaginary part.
With boxed arrays, the ordering is by the contents of each box. The precedence is firstly by type, with numerical arrays preceding empty arrays preceding character arrays preceding boxed arrays:
Within arrays of the same type, lowrank precedes highrank.
Within arrays of the same type and rank, precedence depends on shape and content. If the two arrays are the same, then the earlier takes precedence (that is, their original order is not disturbed). a =: 2 3 $ 1 2 3 4 5 6 b =: 3 2 $ 1 2 5 6 3 4 c =: 1 3 $ 1 2 3 d =: 1 3 $ 1 1 3
16.2.2 UserDefined Collating SequencesThe keys are computed from the data. By choosing how to compute the keys, we can choose a collating sequence. For example, suppose a list of numbers is to be sorted into ascending order of absolute value. A suitable keycomputing function would then be the "Magnitude" function, .
16.3 TranspositionsThe monadic verb : will transpose a matrix, that is, interchange the first and second axes.
More generally, : will reverse the order of the axes of a ndimensional array.
Dyadic transpose will permute the axes according to the (full or abbreviated) permutationvector given as left argument. For a 3dimensional array, all possible permutations are given by (tap 3) 'A B C D E F' =: tap 3
A boxed abbreviated argument can be given. Two or more boxed axisnumbers are run together to form a single axis. With two dimensions, this is equivalent to taking the diagonal.
16.4 Reversing, Rotating and Shifting16.4.1 ReversingMonadic . will reverse the order of the items of its argument.
Notice that "reversing the items" means reversing along the first axis. Reversal along other axes can be achieved with the rank conjunction (").
16.4.2 RotatingDyadic . rotates the items of y by an amount given by the argument x. A positive value for x rotates to the left.
Successive numbers in x rotate y along successive axes:
16.4.3 ShiftingThe items which would be brought around by cyclic rotation can instead be replaced with a fillitem. A shifting verb is written (. !. f) where f is the fillitem. ash =: . !. '*' NB. alphabetic shift nsh =: . !. 0 NB. numeric shift
This is the end of Chapter 16 
Copyright © Roger Stokes 1999. This material may be freely reproduced, provided that this copyright notice and provision is also reproduced.
last updated 10 September 1999