An exact permutation test

Two small groups were measured, for example plants with and without a fertiliser. If the treatment did nothing, the group labels are arbitrary. A permutation test tries every way of relabelling the data and asks how often the difference is as large as the real one.

What to build

A program that runs an exact two-sided permutation test on the difference in means.

Requirements

  • Print difference D, mean(A) − mean(B), to 2 decimal places.
  • Print arrangements T, the number of ways to choose group A's members from all the values.
  • Print p-value P to 4 decimal places: the share of arrangements whose difference has an absolute value at least that of the real one.

Input

Two lines: the values of group A, then the values of group B.

Output

Three lines.

Constraints

Each group has 1 to 6 values; at most 12 values in total.

Example

Input:

5 6 7
1 2 3

Output:

difference 4.00
arrangements 20
p-value 0.1000

Why it works

Under H₀ every split of the pooled values into groups of the same sizes is equally likely, so the p-value is simply the share of splits at least as extreme as the observed one. No normal curve is needed.

Examples

Example 1 · Input
5 6 7
1 2 3
Expected output
difference 4.00
arrangements 20
p-value 0.1000
Example 2 · Input
3 4
1 2
Expected output
difference 2.00
arrangements 6
p-value 0.3333

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Join both groups, then use itertools.combinations to choose which positions form group A.

Hint 2

For each split, work out mean(A) − mean(B) and count the splits at least as extreme as the real one.

Hint 3

Compare absolute values with a small tolerance, such as abs(d) >= abs(observed) - 1e-9.

Solution

Show one correct solution (try it yourself first)
from itertools import combinations

a = list(map(float, input().split()))
b = list(map(float, input().split()))
pool = a + b
total = sum(pool)
observed = sum(a) / len(a) - sum(b) / len(b)
count = splits = 0
for chosen in combinations(range(len(pool)), len(a)):
    sa = sum(pool[i] for i in chosen)
    d = sa / len(a) - (total - sa) / len(b)
    splits += 1
    if abs(d) >= abs(observed) - 1e-9:
        count += 1
print(f"difference {observed:.2f}")
print(f"arrangements {splits}")
print(f"p-value {count / splits:.4f}")

Lesson: Hypothesis testing and p-values →