A permutation test compares two groups by asking how unusual the real split is among all ways of choosing which len(a) of the pooled values form group A. A shuffle-based test only samples those splits. For small groups you could list them all, but two classes of 12 already have C(24, 12) = 2,704,156 splits, and two groups of 20 have 137 billion.
a and b hold whole-number scores. Let N = len(a) + len(b), na = len(a) and total the sum of all scores. Each split chooses na of the N positions for group A (positions, not values: equal scores at different positions are different choices). A split with group-A sum s is at least as extreme as the real one when
|N · s - na · total| >= |N · sum(a) - na · total|
(the distance of s from its expected value na · total / N, multiplied by N so everything stays an integer; this is the two-sided test of the difference in means).
Write exact_shuffle_p(a, b) that returns a tuple (count, splits, p): the number of splits at least as extreme (an integer), the number of all splits C(N, na) (an integer), and p = count / splits.
The setup provides exam_scores(n_a, n_b, gap, seed), which returns a pair (a, b) of whole-number scores with group B gap points better on average.
Examples
Input: a = [3, 5, 4], b = [7, 6, 9, 8]
Output: (2, 35, 0.05714285714285714)
Explanation: of the 35 ways to choose 3 of the 7 values, only {3, 4, 5} (the real one)
and {7, 8, 9} are as far from the expected sum 18 as the real sum 12.
Input: a = [62, 70, 58, 65, 71, 60, 66, 55, 68, 63, 59, 67],
b = [68, 74, 63, 70, 79, 66, 61, 72, 75, 69, 64, 71]
Output: (41616, 2704156, 0.01538964468026253)
Explanation: 10,000 random shuffles estimate this p-value as about 0.015; the exact
value needs no randomness at all.
Constraints
1 <= len(a), len(b)andN <= 40; every score is a whole number from 0 to 100- the whole call must finish well within half a second, so listing the splits is not an option for the larger tests
Goals
- State the exact null distribution of a two-group permutation test as a counting problem
- Count the subsets of each size and sum without listing them
- Compare two groups with integer arithmetic so ties are decided exactly