Help / Learning / Ch 16: Rearrangements

From J Wiki
Jump to navigation Jump to search


>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J


Chapter 16: Rearrangements

This chapter covers rearranging the items of arrays: permuting, sorting, transposing, reversing, rotating and shifting.

16.1 Permutations

A 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:

y =: 'abcde' z =: 4 2 3 1 0 { y
abcde ecdba

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 & {

y p y p p y p p p p p p y
abcde ecdba adbce abcde

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:

C. 4 2 3 1 0 C. 3 1 2 ; 4 0
+-----+---+

|3 1 2|4 0|

+-----+---+
4 2 3 1 0

The dyadic verb C. can accept either form as its left argument, and permutes its right argument.

y 4 2 3 1 0 C. y (3 1 2 ; 4 0) C. y
abcde ecdba ecdba

16.1.1 Abbreviated Permutations

Dyadic 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.

y 2 C. y 2 3 C. y
abcde abdec abecd

With the abbreviated form, successive items are taken from the original vector: notice how the following two examples give different results.

y 2 3 C. y 3 C. (2 C. y)
abcde abecd abdce

If the left argument is boxed, then each box in turn is applied as a cycle:

y (<3 1 2) C. y (3 1 2 ; 4 0) C. y
abcde acdbe ecdba

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:

y a =: 1 3 a C. y f =: a U (#y) f C. y
abcde 1 3 acebd 0 2 4 1 3 acebd

16.1.2 Inverse Permutation

If 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.)

y f z =: f C. y /: f (/: f) C. z
abcde 0 2 4 1 3 acebd 0 3 1 4 2 abcde

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).

A. 2 1 0 5 { tap 3
5 2 1 0

The dyadic verb A. applies an atomic representation of a permutation.

2 1 0 { 'PQR' 5 A. 'PQR'
RQP RQP

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
)
   

LPerms 'abcde'; 0; 4 LPerms 'abcde'; 4; 4
abcde

abced
abdce

abdec
abecd

abedc
acbde

acbed

16.2 Sorting

There 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.

L =: 'barn' /: L
barn 1 0 3 2

These indices select the items of L in ascending order. That is, the expression ((/: L) { L) yields the items of L in order.

L /: L (/: L) { L
barn 1 0 3 2 abnr

For sorting into descending order, the monad \:(backslash colon, called "Grade Down") can be used.

L (\: L) { L
barn rnba

Since L is a character list, its items are sorted into alphabetical order. Numeric lists or boxed lists are sorted appropriately.

N =: 3 1 4 5 (/: N) { N
3 1 4 5 1 3 4 5

B =: 'pooh';'bah';10;5 (/: B) { B
+----+---+--+-+

|pooh|bah|10|5|

+----+---+--+-+
+-+--+---+----+

|5|10|bah|pooh|

+-+--+---+----+

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.

T keys =: 2&{"1 T (/: keys) { T
+---+------+----+

|WA |Mozart|1756|
+---+------+----+
|JS |Bach  |1685|
+---+------+----+
|CPE|Bach  |1714|

+---+------+----+
+----+----+----+

|1756|1685|1714|

+----+----+----+
+---+------+----+

|JS |Bach  |1685|
+---+------+----+
|CPE|Bach  |1714|
+---+------+----+
|WA |Mozart|1756|

+---+------+----+

The expression (/: keys { T) can be abbreviated as (T /: keys), using the dyadic case of /:, (called "Sort")

(/: keys) { T T /: keys
+---+------+----+

|JS |Bach  |1685|
+---+------+----+
|CPE|Bach  |1714|
+---+------+----+
|WA |Mozart|1756|

+---+------+----+
+---+------+----+

|JS |Bach  |1685|
+---+------+----+
|CPE|Bach  |1714|
+---+------+----+
|WA |Mozart|1756|

+---+------+----+

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.

keys =: 1 0 & { " 1 T T /: keys
+------+---+

|Mozart|WA |
+------+---+
|Bach  |JS |
+------+---+
|Bach  |CPE|

+------+---+
+---+------+----+

|CPE|Bach  |1714|
+---+------+----+
|JS |Bach  |1685|
+---+------+----+
|WA |Mozart|1756|

+---+------+----+

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 Sequences

Characters 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.

n=: 0 1 _1 2j1 1j2 1j1 n /: n
0 1 _1 2j1 1j2 1j1 _1 0 1 1j1 1j2 2j1

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:

k=: (< 'abc') ; 'pqr' ; 4 ; '' ; 3 k /: k
+-----+---+-++-+

|+---+|pqr|4||3|
||abc||   | || |
|+---+|   | || |

+-----+---+-++-+
+-+-++---+-----+

|3|4||pqr|+---+|
| | ||   ||abc||
| | ||   |+---+|

+-+-++---+-----+

Within arrays of the same type, low-rank precedes high-rank.

m=: 2 4 ; 3 ; (1 1 $ 1) m /: m
+---+-+-+

|2 4|3|1|

+---+-+-+
+-+---+-+

|3|2 4|1|

+-+---+-+

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
   

u=:a;b;c u /: u
+-----+---+-----+

|1 2 3|1 2|1 2 3|
|4 5 6|5 6|     |
|     |3 4|     |

+-----+---+-----+
+---+-----+-----+

|1 2|1 2 3|1 2 3|
|5 6|     |4 5 6|
|3 4|     |     |

+---+-----+-----+

w=:a;b;c;d w /: w
+-----+---+-----+-----+

|1 2 3|1 2|1 2 3|1 1 3|
|4 5 6|5 6|     |     |
|     |3 4|     |     |

+-----+---+-----+-----+
+-----+---+-----+-----+

|1 1 3|1 2|1 2 3|1 2 3|
|     |5 6|     |4 5 6|
|     |3 4|     |     |

+-----+---+-----+-----+

16.2.2 User-Defined Collating Sequences

The 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, |.

x=: 2 1 _3 keys =: | x x /: keys
2 1 _3 2 1 3 1 2 _3

16.3 Transpositions

The monadic verb |: will transpose a matrix, that is, interchange the first and second axes.

M =: 2 3 $ 'abcdef' |: M
abc
def
ad

be

cf

More generally, |: will reverse the order of the axes of a n-dimensional array.

N =: 2 2 2 $ 'abcdefgh' |: N
ab

cd

ef

gh
ae

cg

bf

dh

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

N 0 1 2 |: N 0 2 1 |: N 1 0 2 |: N
ab

cd

ef

gh
ab

cd

ef

gh
ac

bd

eg

fh
ab

ef

cd

gh

1 2 0 |: N 2 0 1 |: N 2 1 0 |: N
ae

bf

cg

dh
ac

eg

bd

fh
ae

cg

bf

dh

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.

K =: i. 3 3 (< 0 1) |: K
0 1 2

3 4 5

6 7 8
0 4 8

16.4 Reversing, Rotating and Shifting

16.4.1 Reversing

Monadic |. will reverse the order of the items of its argument.

y |. y M |. M
abcde edcba abc
def
def
abc

Notice that "reversing the items" means reversing along the first axis. Reversal along other axes can be achieved with the rank conjunction (").

N |. N |." 1 N |. " 2 N
ab

cd

ef

gh
ef

gh

ab

cd
ba

dc

fe

hg
cd

ab

gh

ef

16.4.2 Rotating

Dyadic |. rotates the items of y by an amount given by the argument x. A positive value for x rotates to the left.

y 1 |. y _1 |. y
abcde bcdea eabcd

Successive numbers in x rotate y along successive axes:

M 1 2 |. M N 1 2 |. N
abc
def
fde
cab
ab

cd

ef

gh
ef

gh

ab

cd

16.4.3 Shifting

The 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
             

y _2 ash y z =: 2 3 4 _1 nsh z
abcde **abc 2 3 4 0 2 3

This is the end of Chapter 16


NEXT
Table of Contents
Index


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