content_image/300097.jpg content_image/300096.jpg content_image/300095.jpg
## 3.1.1 Algorithm for the K -sample problem 

For g = 1 , . . . , K (the categories of X ) and r = 1 , . . . , N (the ranks of Y ), we first compute in O ( N ) A as follows: 

<img src='content_image/300097.jpg'>

and let A ( g, 0) = 0. For a cell with rank range [ r$_{l}$, r$_{h}$ ], where r$_{l}$, r$_{h}$ ∈ { 1 , . . . , N } , using A , the count of observations in category g that fall inside the cell can be computed in O (1) operations as o$_{C}$ ( g ) = A ( g, r$_{h}$ ) − A ( g, r$_{l}$ − 1). Therefore, for each cell C the contribution of the cell, t$_{C}$ , can be computed in O (1) time. 

Because the score per partition is a sum of contributions of individual cells, S$_{m}$ is the sum over the score per cell, multiplied by the number of times the cell appears in a partition of size m . Considering further summing cells of width 1 to N , we may write S$_{m}$ as follows: 

<img src='content_image/300096.jpg'>

where C ( w ) is the collection of cells of width w and n ( w, m, C ) is the number of partitions that include C . For computing n ( w, m, C ), we differentiate between two possible types of cells: edge cells and internal cells. Edge cells differ from internal cells by having either r$_{l}$ = 1 or r$_{h}$ = N . The number of partitions of order m that include an edge cell of width w = r$_{h}$ − r$_{l}$ + 1 is given by ( N − 1 − w m − 2 $^{)}$. The number of partitions including a similarly wide internal cell is ( N − 2 − w m − 3 $^{)}$. Therefore, we may write S$_{m}$ as follows: 

<img src='content_image/300095.jpg'>

