Skip to content

Instantly share code, notes, and snippets.

@lamg
Last active January 12, 2022 21:08
Show Gist options
  • Save lamg/9603c39e7d37cb1916a7e88cf4a3406f to your computer and use it in GitHub Desktop.
Save lamg/9603c39e7d37cb1916a7e88cf4a3406f to your computer and use it in GitHub Desktop.
check if two vectiors are a permutation of the same set
use std::cmp::PartialEq;
fn is_perm<T: PartialEq>(xs: &Vec<T>, ys: &Vec<T>) -> bool {
let mut ok = xs.len() == ys.len();
let mut ws: Vec<&T> = xs.iter().collect();
let mut zs: Vec<&T> = ys.iter().collect();
while ok && ws.len() != 0 {
let (ok0, i) = exists(&zs, &ws[0]);
ok = ok0;
if ok0 {
ws.remove(0);
zs.remove(i);
}
}
ok
}
fn exists<T: PartialEq>(ys: &Vec<T>, v: &T) -> (bool, usize) {
let mut ok = false;
let mut i: usize = 0;
while !ok && i != ys.len() {
ok = &ys[i] == v;
if !ok {
i = i + 1;
}
}
(ok, i)
}
#[cfg(test)]
mod tests {
#[test]
fn test_is_perm() {
let ts = vec![
(vec![0, 2, 1], vec![0, 1, 2], true),
(vec![0], vec![2], false),
(vec![], vec![1], false),
(vec![], vec![], true),
(vec![0, 0, 1], vec![0, 1, 1], false),
];
for j in ts.iter() {
let ok = super::is_perm(&j.0, &j.1);
assert_eq!(j.2, ok);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment