Struct permutation::permutation::Permutation
source · [−]pub struct Permutation { /* private fields */ }
Implementations
👎 Deprecated since 0.4.0: Please replace with oneline(vec).inverse()
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']);
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']);
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]);
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);
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);
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']);
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);
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.
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]));
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);
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);
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);
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']);
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']);
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);
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
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.
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
Mutably borrows from an owned value. Read more