Struct permutation::permutation::Permutation

pub struct Permutation { /* fields omitted */ }

Methods

impl Permutation

fn from_vec(vec: Vec<usize>) -> Permutation

Create a permutation from a vector of indices in one-line notation.

See Wikipedia details about this notation.

Examples

let vec = vec!['a','b','c','d'];
let permutation = Permutation::from_vec(vec![0,2,1,3]);
assert!(permutation.apply_slice(&vec[..]) == vec!['a','c','b','d']);

fn one(len: usize) -> Permutation

Return the identity permutation of size N.

This returns the identity permutation of N elements. in one-line notation, this will just be (0, 1, 2, 3 ,..., N)

Examples

let vec = vec!['a','b','c','d'];
let permutation = Permutation::one(4);
assert!(permutation.apply_slice(&vec[..]) == vec!['a','b','c','d']);

fn len(&self) -> usize

Return the size of a permutation.

This is the number of elements that the permutation acts on.

Examples

use permutation::Permutation;
let permutation = Permutation::one(4);
assert!(permutation.len() == 4);

fn valid(&self) -> bool

Check whether a permutation is valid.

A permutation can be invalid if it was constructed with an incorrect vector using ::from_vec(). Debug assertions will catch this on construction, so it should never return true.

fn inverse(self) -> Permutation

Return the inverse of a permutation.

This returns a permutation that will undo a given permutation. Internally, this does not compute the inverse, but just flips a bit.

let permutation = Permutation::from_vec(vec![0,2,3,1]);
assert!(permutation.inverse() == Permutation::from_vec(vec![0,3,1,2]));

fn normalize(self, backward: bool) -> Permutation

Normalize the internal storage of the Permutation, optimizing it for forward or inverse application.

Internally, the permutation has a bit to indicate whether it is inverted. This is because given a permutation P, it is just as easy to compute P^-1 * Q as it is to compute P * Q. However, computing the entries of P^-1 requires some computation. However, when applying to the permutation to an index, the permutation has a "preferred" direction, which is much quicker to compute.

The normalize() method does not change the value of the permutation, but it converts it into the preferred form for applying P or its inverse, respectively.

If backward is false, it will be in the preferred form for applying P, if backward is true, it will be in the preferred form for appling P^-1

Examples

let permutation = Permutation::from_vec(vec![0, 3, 2, 5, 1, 4]);
let reversed = permutation.inverse().normalize(true);
assert!(reversed.apply_inv_idx(3) == 1);

fn apply_idx(&self, idx: usize) -> usize

Apply the permutation to an index.

Given an index of an element, this will return the new index of that element after applying the permutation.

Examples

let permutation = Permutation::from_vec(vec![0,2,1]);
assert!(permutation.apply_idx(2) == 1);

fn apply_inv_idx(&self, idx: usize) -> usize

Apply the inverse of a permutation to an index.

Given an index of an element, this will return the new index of that element after applying 'P^-1'.

Equivalently, if P.apply_idx(i) == j, then P.apply_inv_idx(j) == i.

Examples

let permutation = Permutation::from_vec(vec![0,2,1]);
assert!(permutation.apply_inv_idx(1) == 2);

fn apply_slice<T: Clone, D>(&self, vec: D) -> Vec<T> where
    D: Deref<Target = [T]>, 

Apply a permutation to a slice of elements

Given a slice of elements, this will permute the elements in place according to this permutation.

Examples

let permutation = Permutation::from_vec(vec![0,3,1,2]);
let vec = vec!['a','b','c','d'];
assert!(permutation.apply_slice(&vec[..]) == vec!['a', 'd', 'b', 'c']);

fn apply_inv_slice<T: Clone, D>(&self, vec: D) -> Vec<T> where
    D: Deref<Target = [T]>, 

Apply the inverse of a permutation to a slice of elements

Given a slice of elements, this will permute the elements in place according to the inverse of this permutation. This is equivalent to "undoing" the permutation.

Examples

let permutation = Permutation::from_vec(vec![0,3,1,2]);
let vec = vec!['a','b', 'c', 'd'];
assert!(permutation.apply_inv_slice(vec) == vec!['a', 'c', 'd', 'b']);

Trait Implementations

impl Clone for Permutation

fn clone(&self) -> Permutation

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Permutation

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl PartialEq for Permutation

fn eq(&self, other: &Permutation) -> bool

This method compares two Permutations for equality, and is uses by ==

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl Eq for Permutation

impl<'a, 'b> Mul<&'b Permutation> for &'a Permutation

type Output = Permutation

The resulting type after applying the * operator

fn mul(self, rhs: &'b Permutation) -> Self::Output

Multiply permutations, in the mathematical sense.

Given two permutations a, and b, a * b is defined as the permutation created by first applying b, then applying a.

Examples

let p1 = Permutation::from_vec(vec![1, 0, 2]);
let p2 = Permutation::from_vec(vec![0, 2, 1]);
assert!(&p1 * &p2 == Permutation::from_vec(vec![2,0,1]));