sim-lib-discrete-rank 0.1.2

Discrete rank adapters.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

//! Nat-valued distance helpers for the discrete rank spaces.
//!
//! All metrics return a `BigUint` count or sum: Hamming, set symmetric
//! difference, Kendall-tau, and L1. Normalized fractional forms (e.g. Jaccard)
//! are the symmetric-difference numerator divided by the union size; the rank
//! layer uses the integer numerator as the coordinate distance.

use num_bigint::BigUint;
use std::collections::{BTreeMap, BTreeSet};

/// Hamming distance between two equal-length bit vectors.
pub fn hamming_bits(a: &[bool], b: &[bool]) -> BigUint {
    let count = a.iter().zip(b).filter(|(x, y)| x != y).count();
    BigUint::from(count)
}

/// Symmetric-difference cardinality of two sets of indices.
pub fn symmetric_difference(a: &[usize], b: &[usize]) -> BigUint {
    let sa: BTreeSet<usize> = a.iter().copied().collect();
    let sb: BTreeSet<usize> = b.iter().copied().collect();
    BigUint::from(sa.symmetric_difference(&sb).count())
}

/// Kendall-tau distance between two permutations of `0..n`: the number of pairs
/// ordered differently.
pub fn kendall_tau(a: &[usize], b: &[usize]) -> BigUint {
    let positions_b: BTreeMap<usize, usize> = b
        .iter()
        .enumerate()
        .map(|(pos, &item)| (item, pos))
        .collect();
    let mut count = 0usize;
    for i in 0..a.len() {
        for j in (i + 1)..a.len() {
            let Some(&pos_i) = positions_b.get(&a[i]) else {
                continue;
            };
            let Some(&pos_j) = positions_b.get(&a[j]) else {
                continue;
            };
            if pos_i > pos_j {
                count += 1;
            }
        }
    }
    BigUint::from(count)
}

/// L1 distance between two equal-length integer vectors.
pub fn l1_u64(a: &[u64], b: &[u64]) -> BigUint {
    let mut acc = BigUint::from(0u32);
    for (x, y) in a.iter().zip(b) {
        acc += BigUint::from(x.abs_diff(*y));
    }
    acc
}

/// L1 distance between two equal-length `i64` coefficient vectors.
pub fn l1_i64(a: &[i64], b: &[i64]) -> BigUint {
    let mut acc = BigUint::from(0u32);
    for (x, y) in a.iter().zip(b) {
        let d = (*x as i128 - *y as i128).unsigned_abs();
        acc += BigUint::from(d);
    }
    acc
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn hamming_counts_differences() {
        assert_eq!(
            hamming_bits(&[true, false, true], &[true, true, false]),
            BigUint::from(2u32)
        );
    }

    #[test]
    fn symmetric_difference_counts() {
        assert_eq!(
            symmetric_difference(&[0, 1, 2], &[1, 2, 3]),
            BigUint::from(2u32)
        );
    }

    #[test]
    fn kendall_tau_basic() {
        // Reversing 3 elements gives 3 discordant pairs.
        assert_eq!(kendall_tau(&[0, 1, 2], &[2, 1, 0]), BigUint::from(3u32));
        assert_eq!(kendall_tau(&[0, 1, 2], &[0, 1, 2]), BigUint::from(0u32));
        assert_eq!(kendall_tau(&[0, 2, 1], &[1, 2, 0]), BigUint::from(3u32));
    }

    #[test]
    fn l1_distances() {
        assert_eq!(l1_u64(&[1, 5, 3], &[4, 1, 3]), BigUint::from(7u32));
        assert_eq!(l1_i64(&[-2, 3], &[1, -1]), BigUint::from(7u32));
    }
}