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.
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 dyadic case of /: allows
the expression (/: keys { T)
to be abbreviated as (T /: keys).
(/: keys) { T |
T /: keys |
+---+------+----+
|JS |Bach |1685|
+---+------+----+
|CPE|Bach |1714|
+---+------+----+
|WA |Mozart|1756|
+---+------+----+ |
+---+------+----+
|JS |Bach |1685|
+---+------+----+
|CPE|Bach |1714|
+---+------+----+
|WA |Mozart|1756|
+---+------+----+ |
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, all possible permutations are
given by (tap 3)
'A B C D E F' =: tap 3
N |
A |: N |
B |: N |
C |: N |
F |: N |
ab
cd
ef
gh |
ab
cd
ef
gh |
ac
bd
eg
fh |
ab
ef
cd
gh |
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
|