Repository Public
1import Foundation2import SheetCore34/// Result of a permutation (randomisation) test.5public struct PermutationTestResult: Sendable, Hashable, Codable, TableReport {6 /// Observed value of the statistic.7 public var statistic: Double8 /// p-value for `alternative`. Exact tests: share of the enumerated arrangements at least as9 /// extreme as the observed one. Monte Carlo tests: (b + 1) / (m + 1) with b extreme resamples out10 /// of m (the observed arrangement counts as one). Two-sided: 2·min(p_less, p_greater), capped at 1.11 public var pValue: Double12 public var alternative: Alternative13 /// True when every distinct arrangement was enumerated.14 public var exact: Bool15 /// Number of arrangements evaluated (enumerated or randomly drawn).16 public var permutations: Int17 /// "independent" (labels reshuffled between two samples) or "paired" (signs of differences flipped).18 public var design: String19 public var seed: UInt64?20 /// Statistic of every arrangement evaluated (the null distribution), in evaluation order.21 public var nullDistribution: [Double]2223 public func table() -> [[Value]] {24 var rows: [[Value]] = [25 [.text("Permutation test"), .blank],26 Report.row("Design", design),27 Report.row("Statistic", statistic),28 Report.row("p-value", pValue),29 Report.row("Alternative", alternative.label),30 Report.row("Method", exact ? "exact (full enumeration)" : "Monte Carlo, p = (b+1)/(m+1)"),31 Report.row("Arrangements evaluated", permutations),32 ]33 if let seed { rows.append([.text("Seed"), .text(String(seed))]) }34 rows.append(Report.row("Assumptions", "Observations are exchangeable under the null hypothesis"))35 return rows36 }37}3839/// Permutation tests for two independent samples and for paired samples.40///41/// The test is exact (every distinct arrangement is enumerated) when the number of arrangements —42/// C(n+m, n) for independent samples, 2ⁿ for pairs — does not exceed `resamples`; otherwise `resamples`43/// random arrangements are drawn with a seeded generator. This is the rule and the p-value44/// convention of `scipy.stats.permutation_test`, including its tolerance for ties with the observed statistic.45public enum PermutationTest {46 /// Two independent samples; `statistic` defaults to the difference of means mean(x) − mean(y).47 /// `.greater` tests whether the statistic is larger than expected under exchangeability.48 public static func twoSample(_ x: [Double], _ y: [Double], alternative: Alternative = .twoSided,49 resamples: Int = 9999, seed: UInt64 = 1,50 statistic: (([Double], [Double]) throws -> Double)? = nil) throws -> PermutationTestResult {51 guard !x.isEmpty, !y.isEmpty else { throw StatError.insufficientData("both samples need at least one observation") }52 guard resamples >= 1 else { throw StatError.invalidInput("resamples must be ≥ 1") }53 let stat = statistic ?? { Descriptive.mean($0) - Descriptive.mean($1) }54 let n = x.count, total = x.count + y.count55 let pooled = x + y56 let observed = try stat(x, y)57 var null = [Double]()58 let arrangements = ResamplingMath.choose(total, n)59 let exact = arrangements <= Double(resamples)60 if exact {61 null.reserveCapacity(Int(arrangements))62 // enumerate the n-subsets of 0..<total in lexicographic order63 var comb = Array(0..<n)64 var inX = [Bool](repeating: false, count: total)65 while true {66 for i in 0..<total { inX[i] = false }67 for i in comb { inX[i] = true }68 var a = [Double](), b = [Double]()69 a.reserveCapacity(n); b.reserveCapacity(total - n)70 for i in 0..<total { if inX[i] { a.append(pooled[i]) } else { b.append(pooled[i]) } }71 null.append(try stat(a, b))72 var i = n - 173 while i >= 0 && comb[i] == total - n + i { i -= 1 }74 if i < 0 { break }75 comb[i] += 176 if i + 1 < n { for j in (i + 1)..<n { comb[j] = comb[j - 1] + 1 } }77 }78 } else {79 var rng = Xoshiro256StarStar(seed: seed)80 null.reserveCapacity(resamples)81 var work = pooled82 for _ in 0..<resamples {83 rng.shuffle(&work)84 null.append(try stat(Array(work[0..<n]), Array(work[n...])))85 }86 }87 return summarise(observed: observed, null: null, exact: exact, alternative: alternative, design: "independent", seed: exact ? nil : seed)88 }8990 /// Paired samples: under the null the sign of each difference xᵢ − yᵢ is arbitrary. `statistic`91 /// receives the (sign-flipped) differences and defaults to their mean.92 public static func paired(_ x: [Double], _ y: [Double], alternative: Alternative = .twoSided,93 resamples: Int = 9999, seed: UInt64 = 1,94 statistic: (([Double]) throws -> Double)? = nil) throws -> PermutationTestResult {95 guard x.count == y.count, !x.isEmpty else { throw StatError.invalidInput("paired test needs two non-empty series of equal length") }96 guard resamples >= 1 else { throw StatError.invalidInput("resamples must be ≥ 1") }97 let stat = statistic ?? { Descriptive.mean($0) }98 let d = zip(x, y).map { $0 - $1 }99 let n = d.count100 let observed = try stat(d)101 var null = [Double]()102 let exact = n < 62 && Double(resamples) >= pow(2, Double(n))103 if exact {104 let count = 1 << n105 null.reserveCapacity(count)106 var flipped = d107 for mask in 0..<count {108 for i in 0..<n { flipped[i] = (mask >> i) & 1 == 1 ? -d[i] : d[i] }109 null.append(try stat(flipped))110 }111 } else {112 var rng = Xoshiro256StarStar(seed: seed)113 null.reserveCapacity(resamples)114 var flipped = d115 for _ in 0..<resamples {116 for i in 0..<n { flipped[i] = rng.next() >> 63 == 1 ? -d[i] : d[i] }117 null.append(try stat(flipped))118 }119 }120 return summarise(observed: observed, null: null, exact: exact, alternative: alternative, design: "paired", seed: exact ? nil : seed)121 }122123 private static func summarise(observed: Double, null: [Double], exact: Bool, alternative: Alternative,124 design: String, seed: UInt64?) -> PermutationTestResult {125 // values within a relative ε of the observed statistic count as ties (as SciPy does), so that126 // rounding in the statistic cannot change the count of "as extreme" arrangements127 let eps = 1e-14128 let gamma = abs(Swift.max(eps, eps * abs(observed)))129 var le = 0, ge = 0130 for v in null { if v <= observed + gamma { le += 1 }; if v >= observed - gamma { ge += 1 } }131 let adj = exact ? 0.0 : 1.0132 let m = Double(null.count)133 let pLess = (Double(le) + adj) / (m + adj), pGreater = (Double(ge) + adj) / (m + adj)134 let p: Double135 switch alternative {136 case .less: p = pLess137 case .greater: p = pGreater138 case .twoSided: p = Swift.min(1, 2 * Swift.min(pLess, pGreater))139 }140 return PermutationTestResult(statistic: observed, pValue: p, alternative: alternative, exact: exact,141 permutations: null.count, design: design, seed: seed, nullDistribution: null)142 }143}144