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 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:
C. 4 2 3 1 0 
C. 3 1 2 ; 4 0 
+++
3 1 24 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 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:
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 fulllength 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 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).
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 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
)
LPerms 'abcde'; 0; 4 
LPerms 'abcde'; 4; 4 
abcde
abced
abdce
abdec 
abecd
abedc
acbde
acbed 
16.2 Sorting
There 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.
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 
+++++
poohbah105
+++++ 
+++++
510bahpooh
+++++ 
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.
T 
keys =: 2&{"1 T 
(/: keys) { T 
++++
WA Mozart1756
++++
JS Bach 1685
++++
CPEBach 1714
++++ 
++++
175616851714
++++ 
++++
JS Bach 1685
++++
CPEBach 1714
++++
WA Mozart1756
++++ 
The dyadic case of /: allows
the expression (/: keys { T)
to be abbreviated as (T /: keys).
(/: keys) { T 
T /: keys 
++++
JS Bach 1685
++++
CPEBach 1714
++++
WA Mozart1756
++++ 
++++
JS Bach 1685
++++
CPEBach 1714
++++
WA Mozart1756
++++ 
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 
+++
MozartWA 
+++
Bach JS 
+++
Bach CPE
+++ 
++++
CPEBach 1714
++++
JS Bach 1685
++++
WA Mozart1756
++++ 
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 Sequences
Characters 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.
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 
++++++
++pqr43
abc   
++   
++++++ 
++++++
34pqr++
   abc
   ++
++++++ 
Within arrays of the same type, lowrank precedes
highrank.
m=: 2 4 ; 3 ; (1 1 $ 1) 
m /: m 
++++
2 431
++++ 
++++
32 41
++++ 
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 31 21 2 3
4 5 65 6 
 3 4 
++++ 
++++
1 21 2 31 2 3
5 6 4 5 6
3 4  
++++ 
w=:a;b;c;d 
w /: w 
+++++
1 2 31 21 2 31 1 3
4 5 65 6  
 3 4  
+++++ 
+++++
1 1 31 21 2 31 2 3
 5 6 4 5 6
 3 4  
+++++ 
16.2.2 UserDefined 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 keycomputing
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 ndimensional 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) 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
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 axisnumbers 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 fillitem.
A shifting verb is written (. !. f) where f is the fillitem.
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
