An algorithm for generating exact Wilcoxon p's

It turns out that the list of outcomes for any given N can be generated from the list of outcomes for the next smaller N. In this discussion we'll let S denote the value denoted elsewhere by S+; that is, we now let S denote the sum of ranks for positive deviations from C. Consider for instance the list already given for N = 3.

<

1	2	3	S
-	-	-	0
+	-	-	1
-	+	-	2
+	+	-	3
-	-	+	3
+	-	+	4
-	+	+	5
+	+	+	6

Each row in this list can generate two rows in the list for N = 4, by separately adding + and - to the end of the row. For instance, the third row - + - generates the two rows

-	+	-	-
-	+	-	+

while the fourth row + + - generates the two rows

+	+	-	-
+	+	-	+

When the original row is followed by a -, then S for the new row equals that for the old row. But when the original row is followed by a +, then S for the new row exceeds S for the old row by the new N. For instance, S for the 3-item row + + - is 1 + 2 + 0 or 3, while S for the row + + - + is 1 + 2 + 0 + 4 or 7.

The following table repeats the number of outcomes yielding each possible value of S when N = 3.

S	Number of outcomes
0	1
1	1
2	1
3	2
4	1
5	1
6	1

But since each of these outcomes can generate two outcomes for N = 4, one with the same value of S and one 4 higher, it follows that we can write a table like the following.

S			Sum
0	1	0	1
1	1	0	1
2	1	0	1
3	2	0	2
4	1	1	2
5	1	1	2
6	1	1	2
7	0	2	2
8	0	1	1
9	0	1	1
10	0	1	1

In this table, the first column after the S column is the list of outcomes for N = 3, and the next column is the same column shifted down 4 places. Thus we see for instance that when N = 4, there are two ways to find S = 4, one in the first column and one in the second. In fact we can simply add the two columns to find the number of outcomes yielding each possible value of S when N = 4. That is done in the final column above. Similarly, to find the outcomes for N = 5, take this final column, also shift it down 5 places, and add the two columns, as shown below.

S			Sum
0	1	0	1
1	1	0	1
2	1	0	1
3	2	0	2
4	2	0	2
5	2	1	3
6	2	1	3
7	2	1	3
8	1	2	3
9	1	2	3
10	1	2	3
11	0	2	2
12	0	2	2
13	0	1	1
14	0	1	1
15	0	1	1

Similar columns for larger values of N are found similarly. In fact one can start with the table for N = 1, which is

S
0	1
1	1

That gives the table for N = 2:

S			Sum
0	1	0	1
1	1	0	1
2	0	1	1
3	0	1	1

That in turn gives the table for N = 3:

S			Sum
0	1	0	1
1	1	0	1
2	1	0	1
3	1	1	2
4	0	1	1
5	0	1	1
6	0	1	1

Starting with the table for N = 1, all tables up to N = 100 or larger can be generated in a trivial amount of computer time.