Lines
100 %
Functions
80 %
Branches
/// Returns true iff the given permutation is a bijective mapping within the 0..max range.
///
/// This check requires O(max) time and space, so it should only be used for testing purposes.
pub fn is_valid_permutation<P>(permutation: P, max: usize) -> bool
where
P: Fn(usize) -> usize,
{
let mut visited = vec![false; max];
for i in 0..max {
// Out of bounds
if permutation(i) >= max {
return false;
}
if visited[permutation(i)] {
visited[permutation(i)] = true;
true
#[cfg(test)]
mod tests {
use rand::seq::SliceRandom;
use crate::is_valid_permutation;
use crate::random_test;
#[test]
#[cfg_attr(miri, ignore)] // Test is too slow under miri
fn test_random_is_valid_permutation() {
random_test(100, |rng| {
// Generate a valid permutation.
let valid_permutation: Vec<usize> = {
let mut order: Vec<usize> = (0..100).collect();
order.shuffle(rng);
order
};
assert!(is_valid_permutation(|i| valid_permutation[i], valid_permutation.len()));
// Generate an invalid permutation (duplicate entries).
let invalid_permutation = [0, 1, 2, 3, 4, 5, 6, 7, 8, 8];
assert!(!is_valid_permutation(
|i| invalid_permutation[i],
invalid_permutation.len()
));
// Generate an invalid permutation (missing entries).
let invalid_permutation = [0, 1, 3, 4, 5, 6, 7, 8];
});