gammalooprs/utils/
linnet_ext.rs

1use linnet::permutation::Permutation;
2
3pub trait FromMappings: Sized {
4    fn from_mappings<I>(mappings: I, size: usize) -> Result<Self, String>
5    where
6        I: IntoIterator<Item = (usize, usize)>;
7}
8
9impl FromMappings for Permutation {
10    /// Creates a permutation from a set of mapping pairs, minimizing changes to other elements.
11    ///
12    /// Takes a collection of (from, to) pairs and constructs a valid permutation that satisfies
13    /// these mappings while keeping other elements as close to their identity positions as possible.
14    ///
15    /// # Arguments
16    ///
17    /// * `mappings` - An iterator of (from, to) pairs where each pair represents `from -> to`
18    /// * `size` - The size of the permutation to create
19    ///
20    /// # Returns
21    ///
22    /// A `Result` containing the permutation if successful, or an error string if the mappings
23    /// are inconsistent or invalid.
24    ///
25    /// # Examples
26    ///
27    /// ```
28    /// # use linnet::permutation::Permutation;
29    /// // Create a permutation where 5->0 and 0->1, others stay in place where possible
30    /// let mappings = vec![(5, 0), (0, 1)];
31    /// let p = Permutation::from_mappings(mappings.iter().copied(), 6).unwrap();
32    /// assert_eq!(p.map(), &[1, 5, 2, 3, 4, 0]);
33    ///
34    /// // Verify the specific mappings work
35    /// assert_eq!(p[5], 0);  // 5 -> 0
36    /// assert_eq!(p[0], 1);  // 0 -> 1
37    /// ```
38    fn from_mappings<I>(mappings: I, size: usize) -> Result<Self, String>
39    where
40        I: IntoIterator<Item = (usize, usize)>,
41    {
42        if size == 0 {
43            return Ok(Self::id(0));
44        }
45
46        // Start with identity
47        let mut map: Vec<usize> = (0..size).collect();
48
49        // owner_of_target[t] = Some(s) iff target t is already taken by source s (forced or assigned)
50        let mut owner_of_target: Vec<Option<usize>> = vec![None; size];
51
52        // forced_sources[s] = true iff s has a forced mapping in the input
53        let mut forced_sources = vec![false; size];
54
55        // 1) Apply and validate forced mappings in O(1) each
56        for (from, to) in mappings {
57            if from >= size || to >= size {
58                return Err(format!(
59                    "Index out of bounds: mapping ({}, {}) for size {}",
60                    from, to, size
61                ));
62            }
63
64            if let Some(prev_from) = owner_of_target[to]
65                && prev_from != from
66            {
67                return Err(format!(
68                    "Target {} is mapped from multiple sources ({} and {})",
69                    to, prev_from, from
70                ));
71            }
72            if forced_sources[from] && map[from] != to {
73                return Err(format!(
74                    "Source {} has conflicting mappings ({} vs {})",
75                    from, map[from], to
76                ));
77            }
78
79            // Record the forced mapping
80            map[from] = to;
81            owner_of_target[to] = Some(from);
82            forced_sources[from] = true;
83        }
84
85        // 2) Keep identities whenever possible (minimal changes)
86        //    If a source s is not forced and its identity target s is free, keep s->s.
87        //    Otherwise, it becomes "displaced" and will be assigned later.
88        let mut displaced_sources: Vec<usize> = Vec::new();
89        for s in 0..size {
90            if forced_sources[s] {
91                continue;
92            }
93            if owner_of_target[s].is_none() {
94                // take the identity slot
95                map[s] = s;
96                owner_of_target[s] = Some(s);
97            } else {
98                // identity target already used by some forced mapping -> displace s
99                displaced_sources.push(s);
100            }
101        }
102
103        // 3) Gather remaining free targets (those without an owner)
104        let mut free_targets: Vec<usize> = Vec::new();
105        for (t, owner) in owner_of_target.iter().enumerate().take(size) {
106            if owner.is_none() {
107                free_targets.push(t);
108            }
109        }
110
111        // Sanity: counts must match, otherwise constraints were inconsistent
112        if displaced_sources.len() != free_targets.len() {
113            return Err("Failed to create valid permutation (inconsistent counts)".to_string());
114        }
115
116        // 4) Assign displaced sources to remaining free targets
117        for (s, t) in displaced_sources.into_iter().zip(free_targets) {
118            // Note: t != s by construction (if t==s, owner_of_target[s] would have been None earlier,
119            // and we would have kept the identity)
120            map[s] = t;
121            owner_of_target[t] = Some(s);
122        }
123
124        // 5) Final uniqueness check (linear)
125        let mut seen = vec![false; size];
126        for &t in &map {
127            if t >= size || std::mem::replace(&mut seen[t], true) {
128                return Err("Failed to create valid permutation".to_string());
129            }
130        }
131
132        Ok(Self::from_map(map))
133    }
134}
135
136#[cfg(test)]
137mod tests {
138    use insta::assert_snapshot;
139    use linnet::permutation::Permutation;
140
141    #[test]
142    fn test_from_mappings_complex() {
143        // Test more complex displacement
144        let mappings = [(0, 3), (1, 0)];
145        let p = Permutation::from_mappings(mappings.iter().copied(), 4).unwrap();
146        assert_eq!(p[0], 3);
147        assert_eq!(p[1], 0);
148
149        assert_snapshot!( format!("{:?}",p.apply_slice([0,1,2,3])),@"[1, 3, 2, 0]");
150    }
151}
gammalooprs/utils/linnet_ext.rs

gammalooprs/utils/
linnet_ext.rs
