Help / Learning / Ch 16: Rearrangements
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J
|
|
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 2|4 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 full-length 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 full-length 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 well-defined 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 order-3 permutation, e.g. 2 1 0, then A. 2 1 0 yields the index in the table (tap 3).
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 permutation-number (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 built-in 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 permutation-vector.
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 date-of-birth 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 expression (/: keys { T) can be abbreviated as (T /: keys), using the dyadic case of /:, (called "Sort")
The dyadic case of \: is similar: it is also called "Sort". 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 permutation-vector 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 well-defined 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 built-in J noun a. gives the value of all 256 characters in "alphabetical" order. Note that upper-case letters come before lower-case 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, low-rank precedes high-rank.
Within arrays of the same type and rank, in effect the arrays are ravelled, and then compared element by element. In this case, 1 2 takes precedence over 1 3 (because 2 < 3), and 3 3 takes precedence over 3 3 3 (because 3 3 is shorter than 3 3 3). 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 User-Defined 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 key-computing 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 n-dimensional array.
Dyadic transpose will permute the axes according to the (full or abbreviated) permutation-vector given as left argument. For a 3-dimensional array, there are 6 possible permutations, with the first being the identity-permutation
A boxed abbreviated argument can be given. Two or more boxed axis-numbers 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 fill-item. A shifting verb is written (|. !. f) where f is the fill-item. ash =: |. !. '*' NB. alphabetic shift
nsh =: |. !. 0 NB. numeric shift
This is the end of Chapter 16 |
The examples in this chapter
were executed using J version 701.
This chapter last updated 15 Dec 2012
Copyright © Roger Stokes 2012.
This material may be freely reproduced,
provided that this copyright notice is also reproduced.
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J