sim_lib_discrete_comb/
permutation.rs

1//! Permutations of `{0, ..., n-1}` in lexicographic order, with Lehmer-code
2//! rank/unrank.
3
4use crate::count::factorial;
5use crate::error::CombError;
6use num_bigint::BigUint;
7
8/// Iterator over permutations of `{0, ..., n-1}` in lexicographic order.
9#[derive(Debug, Clone)]
10pub struct PermutationIter {
11    current: Option<Vec<usize>>,
12}
13
14/// Construct a permutation iterator over `{0, ..., n-1}`.
15pub fn permutations(n: usize) -> PermutationIter {
16    PermutationIter {
17        current: Some((0..n).collect()),
18    }
19}
20
21fn advance(p: &mut [usize]) -> bool {
22    let n = p.len();
23    if n < 2 {
24        return false;
25    }
26    let mut i = n - 1;
27    while i > 0 && p[i - 1] >= p[i] {
28        i -= 1;
29    }
30    if i == 0 {
31        return false;
32    }
33    let mut j = n - 1;
34    while p[j] <= p[i - 1] {
35        j -= 1;
36    }
37    p.swap(i - 1, j);
38    p[i..].reverse();
39    true
40}
41
42impl Iterator for PermutationIter {
43    type Item = Vec<usize>;
44
45    fn next(&mut self) -> Option<Self::Item> {
46        let cur = self.current.clone()?;
47        let mut next = cur.clone();
48        self.current = if advance(&mut next) { Some(next) } else { None };
49        Some(cur)
50    }
51}
52
53fn to_usize(value: &BigUint) -> usize {
54    value.iter_u64_digits().next().unwrap_or(0) as usize
55}
56
57fn validate(perm: &[usize]) -> Result<(), CombError> {
58    let n = perm.len();
59    let mut seen = vec![false; n];
60    for &v in perm {
61        if v >= n || seen[v] {
62            return Err(CombError::InvalidParameters(
63                "not a permutation of 0..n".to_string(),
64            ));
65        }
66        seen[v] = true;
67    }
68    Ok(())
69}
70
71/// The Lehmer-code (lexicographic) rank of `perm`.
72pub fn permutation_rank(perm: &[usize]) -> Result<BigUint, CombError> {
73    validate(perm)?;
74    let n = perm.len();
75    let mut rank = BigUint::from(0u32);
76    for i in 0..n {
77        let smaller = (i + 1..n).filter(|&j| perm[j] < perm[i]).count();
78        rank += BigUint::from(smaller as u64) * factorial((n - 1 - i) as u64);
79    }
80    Ok(rank)
81}
82
83/// The permutation of `{0, ..., n-1}` at lexicographic ordinal `rank`.
84pub fn permutation_unrank(rank: &BigUint, n: usize) -> Result<Vec<usize>, CombError> {
85    let total = factorial(n as u64);
86    if rank >= &total {
87        return Err(CombError::OutOfRange {
88            value: rank.to_string(),
89            bound: total.to_string(),
90        });
91    }
92    let mut avail: Vec<usize> = (0..n).collect();
93    let mut remaining = rank.clone();
94    let mut perm = Vec::with_capacity(n);
95    for i in 0..n {
96        let f = factorial((n - 1 - i) as u64);
97        let idx = to_usize(&(&remaining / &f));
98        remaining %= &f;
99        perm.push(avail.remove(idx));
100    }
101    Ok(perm)
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn lexicographic_order_and_count() {
110        let all: Vec<_> = permutations(3).collect();
111        assert_eq!(all.len(), 6);
112        assert_eq!(all[0], vec![0, 1, 2]);
113        assert_eq!(all[1], vec![0, 2, 1]);
114        assert_eq!(all[5], vec![2, 1, 0]);
115    }
116
117    #[test]
118    fn rank_unrank_round_trip() {
119        for (i, p) in permutations(4).enumerate() {
120            let r = permutation_rank(&p).unwrap();
121            assert_eq!(r, BigUint::from(i as u32));
122            assert_eq!(permutation_unrank(&r, 4).unwrap(), p);
123        }
124    }
125
126    #[test]
127    fn rank_rejects_non_permutation() {
128        assert!(matches!(
129            permutation_rank(&[0, 0, 1]),
130            Err(CombError::InvalidParameters(_))
131        ));
132    }
133}
sim_lib_discrete_comb/permutation.rs

sim_lib_discrete_comb/
permutation.rs
