ここで取り上げるのは，「マン・ホイットニーの U 検定の統計量の分布を求める」アルゴリズムです。

　例えば，

    S. Siegel: Nonparametric Statistics for the behavioral sciences. 
               McGraw-Hill Kogakusha, Tokyo, 1956.
    訳書は，藤本 煕 監訳：ノンパラメトリック統計学, マグロウヒル, 東京, 1983.

# u-statistics1.awk

BEGIN {
   n1 = 10
   n2 = 10
   
   if (n1 > 10 && n2 > 10) {
       printf "死ぬほど時間がかかるかも知れません"
       exit
   }
   total = combination(n1+n2, n2)
   u(n1, n2, 0, n1*n2)
   printf "n1 = %i,  n2 = %i のときの U 統計量の分布\n\n", n1, n2
   printf "%5s%7s%12s%12s%12s\n", "U", "度数", "確率", "累積1", "累積2"
   cum2 = 1
   for (i = 0; i <= n1*n2; i++) {
       cp = p[i]/total
       cum1 += cp
       printf "%5i%7i%12.7f%12.7f%12.7f\n", i, p[i], cp, cum1, cum2
       cum2 -= cp
   }
}

function increment(q, s, n,     i)
{
   for (i = 0; i <= n; i++) {
       q[s+i]++
   }
}

function u(n, m, begin, end)
{
   if (n == 1 || m == 1) {
       increment(p, begin, end-begin)
   }
   else {
       u(n-1, m, begin, begin+(n-1)*m)
       u(n, m-1, end-n*(m-1), end)
   }
}

# n から m （n ≧ m ≧ 0 ）を取り出す組合せを求める
# 使用例： x = combination(10, 5)

function combination(n, m,     i, c) 
{
   c = 1
   k = min(n, n-m)
   for (i = 1; i <= k; i++) {
       c *= (n-i+1)/i
   }
   return c
}

# x, y の小さい方を求める
# 使用例： x = min(10, 5)

function min(x, y)
{
   return (x < y) ? x : y
}