SPB Git

Repository Public

Permutation.swift 7.5 KB 144 lines swift

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
Files main
Menu

Theme