Permutate vector values
There is my Rust Playground to an iterative and the looping variants of vector permutation in Rust language.
As known the iterative variant is a little bit faster.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #[allow(dead_code)] | |
| type TItem = u8; | |
| #[allow(dead_code)] | |
| fn permutate_combinations(alternatives: &[&Vec<TItem>]) -> Vec<Vec<TItem>> { | |
| if alternatives.len() <= 1 { | |
| if alternatives.len() == 1 { | |
| alternatives[0] | |
| .iter() | |
| .map(|alt| vec![*alt]) | |
| .collect::<Vec<Vec<TItem>>>() | |
| } else { | |
| return Vec::new(); | |
| } | |
| } else { | |
| let rest_rslt = permutate_combinations(&alternatives[1..]); | |
| rest_rslt | |
| .iter() | |
| .fold(Vec::<Vec<TItem>>::new(), |mut acc, rslt| { | |
| alternatives[0].iter().for_each(|alt| { | |
| let mut v = vec![*alt]; | |
| v.append(&mut rslt.clone()); | |
| acc.push(v); | |
| }); | |
| acc | |
| }) | |
| } | |
| } | |
| #[allow(dead_code)] | |
| fn permutate_combinations_loop(alternatives: &[&Vec<TItem>]) -> Vec<Vec<TItem>> { | |
| if alternatives.len() <= 1 { | |
| if alternatives.len() == 1 { | |
| alternatives[0] | |
| .iter() | |
| .map(|alt| vec![*alt]) | |
| .collect::<Vec<Vec<TItem>>>() | |
| } else { | |
| return Vec::new(); | |
| } | |
| } else { | |
| let mut result = Vec::<Vec<TItem>>::new(); | |
| let rest_rslt = permutate_combinations(&alternatives[1..]); | |
| for i in 0..rest_rslt.len() { | |
| for alt in alternatives[0] { | |
| let mut v = vec![*alt]; | |
| v.append(&mut rest_rslt[i].clone()); | |
| result.push(v); | |
| } | |
| } | |
| result | |
| } | |
| } | |
| #[cfg(test)] | |
| mod tests { | |
| use crate::{permutate_combinations, permutate_combinations_loop, TItem}; | |
| use std::time::Instant; | |
| #[test] | |
| fn test_permutate_combinations() { | |
| let data = [vec![1u8, 2, 3], vec![4, 5], vec![9], vec![12, 13]]; | |
| let alternatives = data.iter().map(|d| d).collect::<Vec<&Vec<TItem>>>(); | |
| let before = Instant::now(); | |
| for _ in 0..5000 { | |
| let _combinations = permutate_combinations(&alternatives); | |
| } | |
| println!("[permutate_combinations] Elapsed time: {:.2?}", before.elapsed()); | |
| let combinations = permutate_combinations(&alternatives); | |
| assert_eq!(0, combinations.iter().filter(|&v| v.len() != 4).count()); | |
| for c in combinations[0..5].iter() { | |
| let cnt = combinations.iter().filter(|&v| c == v).count(); | |
| assert_eq!(1, cnt); | |
| } | |
| assert_eq!(12, combinations.len()); | |
| } | |
| #[test] | |
| fn test_permutate_combinations_loop() { | |
| let data = [vec![1u8, 2, 3], vec![4, 5], vec![9], vec![12, 13]]; | |
| let alternatives = data.iter().map(|d| d).collect::<Vec<&Vec<TItem>>>(); | |
| let before = Instant::now(); | |
| for _ in 0..5000 { | |
| let _combinations = permutate_combinations_loop(&alternatives); | |
| } | |
| println!("[permutate_combinations_loop] Elapsed time: {:.2?}", before.elapsed()); | |
| let combinations = permutate_combinations_loop(&alternatives); | |
| assert_eq!(0, combinations.iter().filter(|&v| v.len() != 4).count()); | |
| for c in combinations[0..5].iter() { | |
| let cnt = combinations.iter().filter(|&v| c == v).count(); | |
| assert_eq!(1, cnt); | |
| } | |
| assert_eq!(12, combinations.len()); | |
| } | |
| } |