Fifty Shades of J/Chapter 27

From J Wiki
Jump to navigation Jump to search

Table of Contents ... Glossary ... Previous Chapter ... Next Chapter

All but one

Principal Topics

β€œ (rank conjunction) . (suffix), |: (transpose), ~ (passive) determinants, minors, cofactors, subtotallng.

A frequent requirement in applied mathematics and statistics is to evaluate sums and products omitting just one variable or dimension. The notion of β€˜all but one’ can be interpreted in two ways, depending whether the β€˜one’ is to be systematically omitted, or obtained by a merge with an existing dimension, that is by reduction.

Retaining all but one

As an example of the first case, adding or multiplying β€˜all but one’ items in a list progressively can be done by using the hook f-1 ~f which means {f/x}f-1 x, for example :

   i.5
0 1 2 3 4
   (-~+/)i.5        NB. sum 5 items omitting one at a time
10 9 8 7 6
   (%~*/)1+i.5      NB. multiply 5 items omitting one at a time
120 60 40 30 24

This extends readily to objects of higher rank :

    ]b=:i.3 4
0 1  2  3
4 5  6  7
8 9 10 11
   (-"1~+/)b        NB. sums of all rows but one
12 14 16 18
 8 10 12 14
 4  6  8 10
   (-"2~+/"1)b    NB. sums of all columns but one
 6  5  4  3
18 17 16 15
30 29 28 27

The rule is that the rank operand for the left verb should be one greater than that of the right verb.

Generalising β€˜retaining all but one’

Another tool which deals with β€˜retaining all but one’ is the suffix adverb which eliminates n items from a list in all possible ways :

   (1+\.i.5);(2+\.i.5);(3+\.i.5)
β”Œβ”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”
β”‚1 2 3 4β”‚2 3 4β”‚3 4β”‚
β”‚0 2 3 4β”‚0 3 4β”‚0 4β”‚
β”‚0 1 3 4β”‚0 1 4β”‚0 1β”‚
β”‚0 1 2 4β”‚0 1 2β”‚   β”‚
β”‚0 1 2 3β”‚     β”‚   β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”˜

In the J line above + is monadic, which for real numbers is a β€˜do nothing’ verb, that is the left arguments 1, 2 and 3 are not added to elements of i.5 but are arguments of the derived verb +\. which indicate how many items are to be dropped progressively working from the left. The first case with 1 as left argument is thus the β€˜all but one’ case.

An application of this is the calculation of minors of a determinant. Consider the rank 2 object z :

   ]z=:3 3$3 6 7 9 3 2 9 7 7
3 6 7
9 3 2
9 7 7
   (1&(+\.))"2 z    NB. select β€˜all but’ one rows
9 3 2
9 7 7

3 6 7 
9 7 7

3 6 7 
9 3 2

Now combine the structural verb transpose with the adverb suffix to switch rows and columns for all but one row at a time :

   transuff=:1&(|:\.)"2
   <"2 transuff z
β”Œβ”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”
β”‚9 9β”‚3 9β”‚3 9β”‚
β”‚3 7β”‚6 7β”‚6 3β”‚
β”‚2 7β”‚7 7β”‚7 2β”‚
β””β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”˜

and the result is a list of the transposed planes of (1&(+.))"2 z.

Do this twice using the power conjunction to generate three boxes within each of the above boxes; the row/column switch is fortuitously reversed and the minors of z obtained :

   <"2 transuff^:2 z
β”Œβ”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”
β”‚3 2β”‚9 2β”‚9 3β”‚
β”‚7 7β”‚9 7β”‚9 7β”‚
β”œβ”€β”€β”€β”Όβ”€β”€β”€β”Όβ”€β”€β”€β”€
β”‚6 7β”‚3 7β”‚3 6β”‚
β”‚7 7β”‚9 7β”‚9 7β”‚
β”œβ”€β”€β”€β”Όβ”€β”€β”€β”Όβ”€β”€β”€β”€
β”‚6 7β”‚3 7β”‚3 6β”‚
β”‚3 2β”‚9 2β”‚9 3β”‚
β””β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”˜

Define

   minors=:transuff^:2    NB. minors unboxed
   det=:-/ .*             NB. determinant

The determinants of the minors are given by

   ]dz=:det every <"2 minors z
 7  45  36
_7 _42 _33
_9 _57 _45

This is verified by using the verb det dyadically :

   (det z);dz det |:z
β”Œβ”€β”¬β”€β”€β”€β”€β”€β”€β”
β”‚3β”‚3  0 0β”‚
β”‚ β”‚0 _3 0β”‚
β”‚ β”‚0  0 3β”‚
β””β”€β”΄β”€β”€β”€β”€β”€β”€β”˜

It is often convenient to use cofactors, that is the signed determinants of minors. This requires multiplication by a matching matrix whose diagonals are alternately +1 and -1. One way of obtaining this matrix is :

   signs=:monad : '-_1+2*2|+/~i.#y

'

so that

   cof=:signs * det every @<"2@minors
   cof z
 7 _45  36
 7 _42  33
_9  57 _45

To summarise this section :

   transuff=:1&(|:\.)"2                NB. transpose with suffix
   minors=:transuff^:2                 NB. minors unboxed
   det=:-/ .*                          NB. determinant
   signs=:monad :'-_1+2*2|+/~i.#y.'    NB. alternate 1,_1
   cof=:signs * det every@<"2@minors   NB. cofactors

Reducing all but one

Rank again is at the heart of the matter, especially as typical experimental data is structured so that dimensions correspond to variables. However, J inherently structures higher rank data as lists, then lists of lists, lists of lists of lists and so on, which implies a nesting within dimensions which is not usually reflected in the β€˜real world’ variables to which the dimensions correspond. For definiteness use q to demonstrate :

   ]q=:i.2 3 4
 0  1  2  3
 4  5  6  7
 8  9 10 11

12 13 14 15
16 17 18 19
20 21 22 23

The standard definition of rank is:

   rk=:#@$        NB. rank

+/ inserts +'s between the list at the topmost level, thereby reducing rank by one, that is merging planes :

   +/q            NB. equivalent to +/"n q for n>2
12 14 16 18
20 22 24 26
28 30 32 34

Explicit rank conjunctions allows such reduction to take place at any level in the rank hierarchy :

   (+/"1 q);(+/"2 q)    NB. merge cols ; merge rows
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚ 6 22 38β”‚12 15 18 21β”‚
β”‚54 70 86β”‚48 51 54 57β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

Progressive reduction to the level of a rank 1 object is obtained using a recursive verb :

  sum=: sum@(+/)`] @.(=&1@rk)
  sum q

60 66 72 78

The above values are readily verifiable as the column sums of q . To find other such sums, say row sums, transpose the data so as to bring the corresponding dimension to the top level. This suggests a general verb which takes the list i.n and performs the a set of n possible shifts necessary to bring each item in turn into the leading position :

   shifts=:|.each<    NB. all distinct shifts of a list
   shifts i.rk q
β”Œβ”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”
β”‚0 1 2β”‚1 2 0β”‚2 0 1β”‚
β””β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”˜

If the argument to shifts is a list generated by i., the result is left arguments to transpose which provide all the restructured forms of q to which sum can be applied. This in turn is determined by the rank of the data matrix, so define

   targs=:shifts@(i.@rk)  NB. arguments for |:
   targs q
β”Œβ”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”
β”‚0 1 2β”‚1 2 0β”‚2 0 1β”‚
β””β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”˜

The full set of transpositions to supply all possible sums by dimension is then

   transposes=:targs |:each <     NB. reqd. transposes
   transposes q
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚ 0  1  2  3β”‚ 0 12β”‚ 0  4  8β”‚
β”‚ 4  5  6  7β”‚ 1 13β”‚12 16 20β”‚
β”‚ 8  9 10 11β”‚ 2 14β”‚        β”‚
β”‚           β”‚ 3 15β”‚ 1  5  9β”‚
β”‚12 13 14 15β”‚     β”‚13 17 21β”‚
β”‚16 17 18 19β”‚ 4 16β”‚        β”‚
β”‚20 21 22 23β”‚ 5 17β”‚ 2  6 10β”‚
β”‚           β”‚ 6 18β”‚14 18 22β”‚
β”‚           β”‚ 7 19β”‚        β”‚
β”‚           β”‚     β”‚ 3  7 11β”‚
β”‚           β”‚ 8 20β”‚15 19 23β”‚
β”‚           β”‚ 9 21β”‚        β”‚
β”‚           β”‚10 22β”‚        β”‚
β”‚           β”‚11 23β”‚        β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”˜

These values are readily verifiable by summing the columns in the boxes above :

   sum each@transposes q
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚60 66 72 78β”‚66 210β”‚60 92 124β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

To give these sums in dimension order, that is so that the $each of the result matches the shape of q, write

   allsums=:1&|.@(sum each@transposes)
   allsums q
β”Œβ”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚66 210β”‚60 92 124β”‚60 66 72 78β”‚
β””β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

To summarise this section :

   rk=:#@$                      NB. rank
   sum=: sum@(+/)`] @.(=&1@rk)  NB. sum down to rank 1
   shifts=:|.each <             NB. all shifts of i.n
   targs=:shifts@(i.@rk)        NB. arguments for |:
   transposes=:targs |:each <   NB. reqd. transpositions
   allsums=:1&|.@(sum each@transposes)

For comparison, here is a one-liner picked from the J Software forum some years ago which performs the same function by using the power conjunction ^: to apply +/ the requisite number of times with transpositions required between steps as in the version above :

   mt=:(<@(+/^:(<:@rk)@:|:)"0 _~i.@rk)
   mt q
β”Œβ”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚66 210β”‚60 92 124β”‚60 66 72 78β”‚
β””β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

Subtotaling

It can be useful to be able to append such reductions to the original data as in :

   total=:,+/    NB. append totals for leading dimension
   sub=:3 :0
i=.0 [ r=.total y
while.(i<<:rk y)do.r=.total"i r [ i=.i+1 end.
)   
   sub q
 0  1  2  3   6
 4  5  6  7  22
 8  9 10 11  38
12 15 18 21  66

12 13 14 15  54
16 17 18 19  70
20 21 22 23  86
48 51 54 57 210

12 14 16 18  60
20 22 24 26  92
28 30 32 34 124
60 66 72 78 276

Multi-statement lines using [ as a separator as in sub allow something approaching the succinctness of tacit definition. However the individual statements are executed from the right since [ itself is just another verb. It is easy to remember that it is [ rather than ] which is the separator, since, for example, it is 0 to the left which is assigned to i in the first line of sub. As far as the J interpreter is concerned it is really only one line which is executed; multiple lines are essentially just an orthographic device.

Code Summary

minors=: transuff^:2                         NB. minors unboxed
transuff=: 1&(|:\.)"2                        NB. transpose with suffix
det=: -/ .*                                  NB. determinant
cof=: signs * det every@<"2@minors           NB. cofactors
signs=: monad :'-_1+2*2|+/~i.#y.'            NB. alternate 1,_1
transposes=: targs |:each <                  NB. reqd. transpositions
targs=: shifts@(i.@rk)                       NB. arguments for |:
shifts=: |.each <                            NB. all shifts of i.n
rk=: #@$                                     NB. rank
allsums=: 1&|.@(sum each@transposes)         
sum=: sum@(+/)`] @.(=&1@rk)                  NB. sum down to rank 1
total=: ,+/                                  NB. append totals for leading dimension

sub=: 3 :0                                   
i=: 0 [ r=: total y                          
while.(i<<:rk y)do.r=: total"i r [ i=: i+1 end.  
)

Script

File:Fsojc27.ijs