Struct permutation::permutation::Permutation
source · [−]pub struct Permutation { /* private fields */ }
Implementations
sourceimpl Permutation
impl Permutation
sourcepub fn from_vec<V>(vec: V) -> Permutation where
V: Into<Vec<usize>>,
👎 Deprecated since 0.4.0: Please replace with oneline(vec).inverse()
pub fn from_vec<V>(vec: V) -> Permutation where
V: Into<Vec<usize>>,
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']);
sourcepub fn oneline<V>(vec: V) -> Permutation where
V: Into<Vec<usize>>,
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']);
sourcepub fn assign_from_sort<T, S>(&mut self, slice: S) where
T: Ord,
S: AsRef<[T]>,
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]);
sourcepub fn assign_from_sort_by<T, S, F>(&mut self, slice: S, compare: F) where
S: AsRef<[T]>,
F: FnMut(&T, &T) -> Ordering,
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);
sourcepub 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,
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);
sourcepub fn one(len: usize) -> Permutation
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']);
sourcepub fn len(&self) -> usize
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);
sourcepub fn valid(&self) -> bool
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.
sourcepub fn inverse(self) -> Permutation
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]));
sourcepub fn normalize(self, backward: bool) -> Permutation
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);
sourcepub fn apply_idx(&self, idx: usize) -> usize
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);
sourcepub fn apply_inv_idx(&self, idx: usize) -> usize
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);
sourcepub fn apply_slice<T: Clone, S>(&self, slice: S) -> Vec<T> where
S: AsRef<[T]>,
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']);
sourcepub fn apply_inv_slice<T: Clone, S>(&self, slice: S) -> Vec<T> where
S: AsRef<[T]>,
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']);
sourcepub fn apply_slice_in_place<T, S>(&mut self, slice: &mut S) where
S: AsMut<[T]> + ?Sized,
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);
sourcepub fn apply_inv_slice_in_place<T, S>(&mut self, slice: &mut S) where
S: AsMut<[T]> + ?Sized,
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
sourceimpl Clone for Permutation
impl Clone for Permutation
sourcefn clone(&self) -> Permutation
fn clone(&self) -> Permutation
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
sourceimpl Debug for Permutation
impl Debug for Permutation
sourceimpl<'a, 'b> Mul<&'b Permutation> for &'a Permutation
impl<'a, 'b> Mul<&'b Permutation> for &'a Permutation
sourcefn mul(self, rhs: &'b Permutation) -> Self::Output
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
type Output = Permutation
The resulting type after applying the *
operator.
sourceimpl PartialEq<Permutation> for Permutation
impl PartialEq<Permutation> for Permutation
impl Eq for Permutation
Auto Trait Implementations
impl RefUnwindSafe for Permutation
impl Send for Permutation
impl Sync for Permutation
impl Unpin for Permutation
impl UnwindSafe for Permutation
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more