# Fifty Shades of J/Chapter 07

(Redirected from Fifty Shades of J/Chapter 7)

### Principal Topics

/: (grade up) : (grade down) |: (transpose) a. (alphabet) ? (deal), “ (rank conjunction) sorting, ranking, collating sequence, tied ranks, schoolmasters rank, reflections, rotations, mean, median

### Sorting Lists

A Vector obituary preview column? Well not quite, or maybe the answer should be, of a sort, since that is what grade (used generically to refer to both the grade up and grade down verbs) is all about. Sorting a list (the equivalent of APL V[⍋V]) has a direct J equivalent in the following bridge hook

```    ({~/:)4 2 7 1
1 2 4 7
```

The algorithm applies equally to character lists

```   ({~/:)>'Fred';'Joe';'Egbert'
Egbert
Fred
Joe
```

For convenience give names to the verbs which sort lists up and down

```  sortu=:{~/:
sortd=:{~\:
sortd>'Fred';'Joe';'Egbert'
Joe
Fred
Egbert
```

Sort by rows and sort within rows are differentiated by using the rank (") conjunction

```   ]u=:?3 4\$10
4 0 1 2
7 9 3 2
1 2 9 5
(sortu u);sortu"1 u
┌───────┬───────┐
│1 2 9 5│0 1 2 4│
│4 0 1 2│2 3 7 9│
│7 9 3 2│1 2 5 9│
└───────┴───────┘
```

For sort by columns do a row sort under (&.) the transformation (|:) (transpose)

```   sortu&.|: u
0 1 2 4
9 3 2 7
2 9 5 1
```

Flexibility in the choice of collating sequence (say all the odd numbers are to be prior to any of the evens) is achieved by using dyadic i.

```   oe=:1 3 5 7 0 2 4 6 8
(/:oe i.v){v=.4 2 7 1
1 7 2 4
```

Consolidate this in a verb

```   csortu=:/:@i.{]            NB. x is collating seq.
oe csortu 4 2 7 1
1 7 2 4
```

Here is a collating sequence which blurs the distinction between uppercase and lowercase characters

```   ]cs=:(,|:65 97+every <i.26){a.
m=:>'bless';'This ';'house'
(];sortu;cs&csortu)m
┌─────┬─────┬─────┐
│bless│This │bless│
│This │bless│house│
│house│house│This │
└─────┴─────┴─────┘
```

Whereas dyadic grade in APL provides a means of changing the collating sequence, this is not the case in J where the following rule for dyadic grade-up applies

```x/:y is equivalent to (/:y){x
```

so that x must be at least as long as y . A special case satisfying this constraint is when x and y are equal, in which case y/:y (or equivalently /:~y) is simply another definition of sortu. The definitions of sortu and sortd can therefore be shortened by one character to

```   sortu=:/:~
sortd=:\:~
```

Sorting by columns of a matrix other than the first requires dyadic grade. The following display demonstrates sorting on the 2nd and 4th columns.

```   colsort=:] /: {"1
(];1&colsort;3&colsort)u
┌───────┬───────┬───────┐
│4 0 1 2│4 0 1 2│4 0 1 2│
│7 9 3 2│1 2 9 5│7 9 3 2│
│1 2 9 5│7 9 3 2│1 2 9 5│
└───────┴───────┴───────┘
```

It is worth while pausing to consider how this fork works. The verb from ({) at rank 1 on the right of the fork selects the chosen column as y , ] selects the entire table as x . Now apply the dyadic grade rule above. The indices for ordering the chosen column are obtained as /:y and are used to select from all the columns in the table.

When items within matrices have complex structures as in data base tables the principle remains unchanged but some minor variations may be necessary involving the use of open (>) and @: to take care of rank inheritance

```   selectc=:>@{"1         NB. select xth column of y
sortc=:/:@:selectc { ]    NB. order y by column x
dbase=:'York';'England';100000
dbase=:|:('Edinburgh';'Scotland';500000),.dbase
dbase=:('Aberdeen';'Scotland';200000),dbase
]dbase=:('Bristol';'England';400000),dbase
┌─────────┬────────┬──────┐
│Bristol  │England │400000│
├─────────┼────────┼──────┤
│Aberdeen │Scotland│200000│
├─────────┼────────┼──────┤
│Edinburgh│Scotland│500000│
├─────────┼────────┼──────┤
│York     │England │100000│
└─────────┴────────┴──────┘
1&sortc dbase        NB. sort by country
┌─────────┬────────┬──────┐
│Bristol  │England │400000│
├─────────┼────────┼──────┤
│York     │England │100000│
├─────────┼────────┼──────┤
│Aberdeen │Scotland│200000│
├─────────┼────────┼──────┤
│Edinburgh│Scotland│500000│
└─────────┴────────┴──────┘
2&sortc dbase            NB. sort by population
┌─────────┬────────┬──────┐
│York     │England │100000│
├─────────┼────────┼──────┤
│Aberdeen │Scotland│200000│
├─────────┼────────┼──────┤
│Bristol  │England │400000│
├─────────┼────────┼──────┤
│Edinburgh│Scotland│500000│
└─────────┴────────┴──────┘
```

### Ranking

The potential confusion between rank in the J sense (as in rank conjunction) and rank in the sense of collating sequence ordering can be avoided by referring to the latter as ranking.

It might be expected that, by analogy with APL, /:/:v delivers the upward ranking of the elements of v

```    /:/:4 2 7 1
2 1 3 0
```

However, if /:/: is isolated by parens around the functions or named, then they are evaluated differently, i.e.

```    (/:/:)4 2 7 1
7 2 1 4
```

The reason is that /:/: by itself is a hook.The rightmost /: obtains the upward ordering index vector of v which is 3 1 0 2 , which, in the absence of an explicit left argument is both left and right argument to the leftmost dyadic /: . Following the rule above, a second grade-up is performed resulting in the intermediate generation of the rank list 2 1 3 0 which is then applied as a selection list (from) on the original right argument leading to the result 7 2 1 4. To block this last step it is necessary to use a different composition mechanism for the two /: verbs, viz.

```   (rku=:/:@/:)4 2 7 1
2 1 3 0
```

```     (rkd=:/:@\:)4 2 7 1
1 2 0 3
```

Upward and downward tied ranks require slightly unwieldy verb combinations

```   rktu=:-:@(rku + \:@/:@|.)
rktd=:-:@(rkd + \:@\:@|.)
rktu v1=:5 3 3 5 2 5 8
4 1.5 1.5 4 0 4 6
rktd v1
2 4.5 4.5 2 6 2 0
```

A variation of rktd is Schoolmaster’s Rank in which students with equal scores are each rated as highly as possible, a property inherent in dyadic i. . The work for the Schoolmaster’s Ranking verb has largely been done and it can be achieved by a single fork

```    sch=:i.~{rkd
>:sch v1
2 5 5 2 7 2 1
```

The grade verbs have applications outside the realm of strict sorting. In Essay #30: Just what do they sell at C&A? grade-up is used to perform inverse permutations, that to reverse the effects of a shuffle. In technical terms, when the argument y is a permutation, that is an arrangement of all the items in i.n where n is a positive integer, then /: is a self-inverse verb, and so in these circumstances /:/:y is identical to y .

Then in Essay #26: Working in Groups it transpires that the application of grade verbs to permutations matched exactly the transformations of rotations and reflections about axes in the plane applied to matrices which provide alternative representations of the permutation in the sense that e.g. 1 0 2 3 is represented by

``` . 1 . .
1 . . .
. . 1 .
. . . 1
```

Specifically /: is a reflection in the line x+y=0 but \: is a clockwise rotation through 90 degrees. The reflection/rotation distinction underlines the non-symmetrical behaviour of /: and \: in the ranking algorithms given above. /:@\: and /:@\: represent reflections in the x- and y-axes, \:@\:@\: represents an anti-clockwise rotation through 90 degrees and \:@\: represents a half-turn. Finally /:@\:@\: represents a reflection in the line x=y.

Order statistics, such as median, require the use of grade. A median algorithm can be built up using three auxiliary verbs

```   mindex=:-:@<:@#    NB. 0.5*(n-1), n=length of vector y
minmax=:<. , >.    NB. floor,ceiling of real number y
mean=:+/%#        NB. arithmetic mean
median=:mean @ ((minmax@mindex) { sortu)
median 4 2 7 1    NB.mean of two middle values
3
```

Now introduce sortu as the right prong of a fork, and use mean to average the values of the two (possibly identical) middle values

```   median=:mean @ ((minmax@mindex) { sortu)
median 4 2 7 1    NB.mean of two middle values
3
```

Verbs defining other partition values, e.g. percentiles, use the same principle, although inevitably are more complex in detail.

In short, grade is a very versatile verb for which you should rightly have grade expectations. Have a grade day!

### Code Summary

```sortu=:/:~                                  NB. sort upwards
sortd=:\:~                                  NB. sort downwards
cs=:(,|:65 97+every <i.26){a.               NB. alphabet AaBbCc…
colsort=:] /: {"1                           NB. sort matrix by columns
selectc=:>@{"1                              NB. select xth column of y
sortc=:/:@:selectc { ]                      NB. order y by column x
rku=:/:@/:                                  NB. upward ranking
rkd=:/:@\:                                  NB. downward ranking
rktu=:-:@(rku + \:@/:@|.)                   NB. upward ranking with ties
rktd=:-:@(rkd + \:@\:@|.)                   NB. downward ranking with ties
sch=:i.~{rkd                                NB. schoolmaster’s ranking
mindex=:-:@<:@#                             NB. 0.5*(n-1) where n is length of vector y
minmax=:<. , >.                             NB. floor,ceiling of real number y
mean=:+/%#                                  NB. arithmetic mean
median=:mean @ ((minmax@mindex) { sortu)
```