# 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

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.

`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 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

NEXT
Table of Contents
Index

Copyright © Roger Stokes 2003. This material may be freely reproduced, provided that this copyright notice is also reproduced.

last updated 12 Sep 2003