Struct Permutation

pub struct Permutation { /* private fields */ }

Implementations

impl Permutation

pub fn from_vec<V>(vec: V) -> Permutation

where V: Into<Vec<usize>>,

👎Deprecated since 0.4.0: Please replace with oneline(vec).inverse()

Create a permutation from a vector of indices.

from_vec(v) returns the permutation P such that P applied to [1,2,…,N] is v. Note that this notation is the inverse of the usual one-line notation used in mathematics. This is a known issue and may change in a newer release.

Examples

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

pub fn oneline<V>(vec: V) -> Permutation

where V: Into<Vec<usize>>,

Create a permutation from zero-based oneline notation

This creates a permutation from one-line notation notation used in mathematics, but using zero-based indices rather than the one-based indices typically used in mathematics.

Note that this is the inverse notation used by the deprecated Permutation::from_vec().

Examples

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

pub fn assign_from_sort<T, S>(&mut self, slice: S)

where T: Ord, S: AsRef<[T]>,

Computes the permutation that would sort a given slice.

This is the same as permutation::sort(), but assigned in-place to self rather than allocating a new permutation.

Panics

If self.len() != vec.len()

Examples

// Say you have a permutation that we don't need anymore...
let mut permutation = permutation::sort(&[0,1,2]);

// You can reuse it rather than allocating a new one, as long as the length is the same
let mut vec = vec!['z','w','h'];
permutation.assign_from_sort(&vec);
let permuted = permutation.apply_slice(&vec);
vec.sort();
assert_eq!(vec, permuted);

// You can also use it to sort multiple arrays based on the ordering of one.
let names = vec!["Bob", "Steve", "Jane"];
let salary = vec![10, 5, 15];
permutation.assign_from_sort(&salary);
let ordered_names = permutation.apply_slice(&names);
let ordered_salaries = permutation.apply_slice(&salary);
assert_eq!(ordered_names, vec!["Steve", "Bob", "Jane"]);
assert_eq!(ordered_salaries, vec![5, 10, 15]);

pub fn assign_from_sort_by<T, S, F>(&mut self, slice: S, compare: F)

where S: AsRef<[T]>, F: FnMut(&T, &T) -> Ordering,

Computes the permutation that would sort a given slice by a comparator.

This is the same as permutation::sort_by(), but assigned in-place to self rather than allocating a new permutation.

Panics

If self.len() != vec.len()

Examples

// Say you have a permutation that we don't need anymore...
let mut permutation = permutation::sort(&[0,1,2,3,4,5]);

// You can assign to it rather than allocating a new one, as long as the length is the same
let mut vec = vec!['z','w','h','a','s','j'];
permutation.assign_from_sort_by(&vec, |a, b| b.cmp(a));
let permuted = permutation.apply_slice(&vec);
vec.sort_by(|a,b| b.cmp(a));
assert_eq!(vec, permuted);

pub fn assign_from_sort_by_key<T, S, B, F>(&mut self, slice: S, f: F)

where B: Ord, S: AsRef<[T]>, F: FnMut(&T) -> B,

Computes the permutation that would sort a given slice by a key function.

This is the same as permutation::sort_by_key(), but assigned in-place to self rather than allocating a new permutation.

Panics

If self.len() != vec.len()

Examples

// Say you have a permutation that we don't need anymore...
let mut permutation = permutation::sort(&[0,1,2,3,4,5]);

// You can assign to it rather than allocating a new one, as long as the length is the same
let mut vec = vec![2, 4, 6, 8, 10, 11];
permutation.assign_from_sort_by_key(&vec, |a| a % 3);
let permuted = permutation.apply_slice(&vec);
vec.sort_by_key(|a| a % 3);
assert_eq!(vec, permuted);

pub fn one(len: usize) -> Permutation

Return the identity permutation of size N.

This returns the identity permutation of N elements.

Examples

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

pub 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_eq!(permutation.len(), 4);

pub 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() or ::oneline().
Debug assertions will catch this on construction, so it should never return true.

pub 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::oneline([0,2,3,1]);
assert_eq!(permutation.inverse(), Permutation::oneline([0,3,1,2]));

pub 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::oneline([0, 3, 2, 5, 1, 4]);
let reversed = permutation.inverse().normalize(true);
assert_eq!(reversed.apply_inv_idx(3), 5);

pub 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.

Note that the running time will be O(1) or O(N) depending on how the permutation is normalized (see Permutation::normalize).

Examples

let permutation = Permutation::oneline([0,2,1]);
assert_eq!(permutation.apply_idx(1), 2);

pub 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.

Note that the running time will be O(1) or O(N) depending on how the permutation is normalized (see Permutation::normalize).

Examples

let permutation = Permutation::oneline([0,2,1]);
assert_eq!(permutation.apply_inv_idx(2), 1);

pub fn apply_slice<T: Clone, S>(&self, slice: S) -> Vec<T>

where S: AsRef<[T]>,

Apply a permutation to a slice of elements

Given a slice of elements, this will permute the elements according to this permutation and clone them to a Vec.

Examples

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

pub fn apply_inv_slice<T: Clone, S>(&self, slice: S) -> Vec<T>

where S: AsRef<[T]>,

Apply the inverse of a permutation to a slice of elements

Given a slice of elements, this will permute the elements according to the inverse of this permutation and clone them to a Vec. This is equivalent to “undoing” the permutation.

Examples

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

pub fn apply_slice_in_place<T, S>(&mut self, slice: &mut S)

where S: AsMut<[T]> + ?Sized,

Apply a permutation to a slice of elements

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

This method borrows self mutably to avoid allocations, but the permutation will be unchanged after it returns.

Panics

If slice.len() != self.len(). If slice.len() > isize::max_value(), due to implementation reasons.

Examples

let mut permutation = Permutation::oneline([0,3,1,2]);
let mut vec = vec!['a', 'b', 'c', 'd'];
let permutation_old = permutation.clone();
permutation.apply_slice_in_place(&mut vec);
assert_eq!(vec, vec!['a', 'c', 'd', 'b']);
assert_eq!(permutation, permutation_old);

pub fn apply_inv_slice_in_place<T, S>(&mut self, slice: &mut S)

where S: AsMut<[T]> + ?Sized,

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.

This method borrows self mutably to avoid allocations, but the permutation will be unchanged after it returns.

Panics

If slice.len() != self.len(). If slice.len() > isize::max_value(), due to implementation reasons.

Examples

let mut permutation = Permutation::oneline([0,3,1,2]);
let mut vec = vec!['a', 'b', 'c', 'd'];
permutation.apply_inv_slice_in_place(&mut vec);
assert_eq!(vec, vec!['a', 'd', 'b', 'c']);

Trait Implementations

impl Clone for Permutation

fn clone(&self) -> Permutation

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Permutation

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

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

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::oneline([1, 0, 2]);
let p2 = Permutation::oneline([0, 2, 1]);
assert_eq!(&p1 * &p2, Permutation::oneline([1,2,0]));

type Output = Permutation

The resulting type after applying the * operator.

impl PartialEq for Permutation

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

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

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for Permutation