mixle.stats.rankings._permutation_kernels module¶
Numba permutation-distance kernels shared by the ranking distributions.
Every right-invariant permutation distance d(a, b) between two orderings (a[r] / b[r] is the
item at rank r) is a function of the single relative-rank permutation r, where r[i] is the
rank, under b, of the item placed at rank i by a (r = rank_b[a]). Writing each distance
as a property of r versus the identity lets one O(n^2)/O(n log n) integer kernel serve all of them:
Kendall tau inversions(r) (discordant pairs) Cayley n - cycles(r) (minimum transpositions) Hamming #{i : r[i] != i} (displaced items) footrule sum_i |r[i] - i| (Spearman footrule, L1) Spearman rho sum_i (r[i] - i)^2 (squared L2) Ulam n - LIS(r) (n - longest increasing subsequence)
All kernels are @numba.njit(cache=True) integer loops, so they JIT to native code and fall back to
pure Python (via the numba shim) when numba is absent – the results are identical either way.
- metric_id(metric)[source]
Map a metric name to its integer id (raises on an unknown name).
- ryser_log_permanent(M)[source]
log permanent of a non-negative matrix via Ryser’s formula with Gray-code subset enumeration.
- sinkhorn_bethe(s, n_iter)[source]
Log-domain Sinkhorn on the kernel
exp(s): returns the doubly-stochastic marginalsPand a Bethe estimate oflog permanent(exp(s))(the scalable approximation for the assignment model).
- relative_ranks(orderings, rank_center)[source]
Compose orderings into the center’s rank frame:
R[k, i] = rank_center[orderings[k, i]].
- seq_distance_to_center(orderings, rank_center, metric)[source]
Vectorized distance of each ordering (row of an
(N, n)array) to the center, undermetric.
- seq_rim_code(orderings, sigma0)[source]
RIM insertion codes
(N, n-1)of each ordering relative to the central permutationsigma0.