In place permutation iterator in Rust.

perm_ives.rs

enum IteratorState {
    First,
    HasNext,
    Done,
}

pub struct PermutationInPlace<'a, T> {
    state: IteratorState,
    counter: Vec<usize>,
    data: &'a mut Vec<&'a T>,
    original_permutation_by_address: Vec<*const T>,
}

impl<'a, T> PermutationInPlace<'a, T> {
    /// Implements [1] as an iterator for generating permutations iteratively with minimal state.
    ///
    /// Permutes the elements of the given vector in place and exposes a reference to the permuted
    /// vector as an iterator.
    ///
    /// The benefit of this implementation is that it is memory-efficient and does not require any
    /// allocations or temporary storage while running the iterator. It works on references, so no
    /// copies are made. These considerations are important if you're stuck with a problem that all
    /// you can do is brute-force it.
    ///
    ///  [1] F. M. Ives. 1976. Permutation enumeration: four new permutation algorithms.
    /// Commun. ACM 19, 2 (Feb. 1976), 68–72. https://doi.org/10.1145/359997.360002
    ///
    ///       # Arguments
    ///
    /// * `data`: Vector of references to be permuted.
    ///
    /// returns: PermutationIves<T> Iterator
    ///
    /// # Examples
    /// Find a permutation of 'data' where the first element is '1' and the last element is '2'.
    /// ```
    ///  let mut data = vec![&1, &2, &3, &4];
    /// `let permutations = PermutationInPlace::new(&mut data);                    ``
    ///  let mut last: Option<_> = None;
    ///  for x in permutations {
    ///      // We want a pattern that starts with 1 and ends with 2.
    ///      if let [&1, _, _, &2 ] = x[..] {
    ///          last = Some(x);
    ///          break;
    ///      }
    ///  }
    /// ```
    pub fn new(data: &'a mut std::vec::Vec<&'a T>) -> Self {
        let mut counter = Vec::new();
        let mut perm = Vec::new();
        for i in 0..data.len() {
            counter.push(i);
            perm.push(data[i] as *const T);
        }
        PermutationInPlace {
            state: IteratorState::First,
            counter,
            data,
            original_permutation_by_address: perm,
        }
    }
}

// Implement the Iterator trait
impl<'a, T> Iterator for PermutationInPlace<'a, T>
    where
        T: 'a,
{
    type Item = &'a mut Vec<&'a T>;
    fn next(&mut self) -> Option<Self::Item> {
        let data = &mut self.data as *mut &mut Vec<&'a T>;
        match self.state {
            IteratorState::First => {
                self.state = IteratorState::HasNext;
                unsafe { Some(&mut *data) }
            }
            IteratorState::Done => None,
            IteratorState::HasNext => {
                let mut low_index = 0;
                let mut high_index = self.data.len() - 1;

                while high_index > low_index {
                    let current_count = self.counter[low_index];
                    if current_count < high_index {
                        self.data.swap(current_count, current_count + 1);
                        self.counter[low_index] += 1;
                        break;
                    }
                    let address_original_perm_position = self.data[low_index] as *const T;
                    self.counter[low_index] = low_index;
                    self.data.swap(low_index, high_index);
                    if address_original_perm_position != self.original_permutation_by_address[high_index] {
                        break;
                    }
                    high_index -= 1;
                    low_index += 1;
                }

                if high_index <= low_index {
                    self.state = IteratorState::Done;
                    None
                } else {
                    self.state = IteratorState::HasNext;
                    unsafe {
                        Some(&mut *data)
                    }
                }
            }
        }
    }
}

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

    #[test]
    fn test_perm() {
        let mut data = vec![&1, &2, &3];
        let permutations = PermutationInPlace::new(&mut data);
        let mut last: Option<_> = None;
        for x in permutations {
            // We're interested in the last one, for instance.
            last = Some(x);
        }
        dbg!(last);
    }

    #[test]
    fn test_big_perm() {
        let mut data = vec![&1, &2, &3, &4, &5, &6, &7, &8, &9, &10, &11, &12, &13];
        let permutations = PermutationInPlace::new(&mut data);
        let mut last: Option<_> = None;
        for x in permutations {
            // We're interested in the last one, for instance.
            last = Some(x);
        }
    }

    #[test]
    fn test_perm_with_pattern() {
        let mut data = vec![&1, &2, &3, &4];
        let permutations = PermutationInPlace::new(&mut data);
        let mut last: Option<_> = None;
        for x in permutations {
            // We want a pattern that starts with 1 and ends with 2.
            if let [&1, _, _, &2 ] = x[..] {
                last = Some(x);
                break;
            }
        }
        dbg!(last);
    }

    #[test]
    fn test_lifetime() {
        // The data comes from here.
        let mut data = vec![&1, &2, &3, &4];
        fn get_target<'a>(data: &'a mut Vec<&'a i32>) -> Option<&'a mut Vec<&'a i32>> {
            for x in PermutationInPlace::new(data) {
                // We want a pattern that starts with 1 and ends with 2.
                if let [&1, _, _, &2 ] = x[..] {
                    return Some(x);
                }
            }
            None
        }
        let target_permutation = get_target(&mut data);
        dbg!(target_permutation);
    }

    // #[bench]
    // fn bench_perm(b: &mut test::Bencher) {
    //     b.iter(move || {
    //         let mut data = vec![&1, &2, &3, &4, &5, &6, &7, &8, &9, &10, &11];
    //         for x in PermutationInPlace::new(&mut data) {
    //             // We're interested in the last one, for instance.
    //         }
    //     });
    // }

    #[test]
    fn test_perm_non_copy() {
        // Simple non-copy example.
        #[derive(Debug)]
        enum Animal<'a> {
            Cow(&'a str),
            Dog,
            Cat,
            Horse,
        }
        use Animal::*;
        let moo_cow = Cow("Moo");
        let mut data = vec![&moo_cow, &Dog, &Cat, &Horse];
        for x in PermutationInPlace::new(&mut data) {
            // Let's look at those pointer addresses. We're not making copies.
            let y = x[0] as *const Animal;
            dbg!(y);
            dbg!(x);
        }
    }
}