Struct Perm 

pub struct Perm { /* private fields */ }

Represents a reordering operation on an array.

See the Permute trait for more information.

Implementations

impl Perm

pub fn eye(n: usize) -> Perm

Construct the identity perm of a given length.

pub fn len(&self) -> usize

Get the length of the permutation.

pub fn argsort<T: Ord>(xs: &[T]) -> Perm

Compute the Perm that, when applied to the input slice, would (stably) sort it.

pub fn argsort_unstable<T: Ord>(xs: &[T]) -> Perm

Compute a Perm that, when applied to the input slice, would sort it. (not necessarily stably)

pub fn from_vec(vec: Vec<usize>) -> Result<Perm, InvalidPermutationError>

Construct a perm. Useful for literals in unit tests.

The representation accepted by this is comparable to indexing with an integer array in numpy. If the kth element of the permutation vector is value, then applying the permutation will pull the data at index value into index k.

This performs O(n log n) validation on the data to verify that it satisfies the invariants of Perm. It also inverts the perm (an O(n) operation).

pub fn from_raw_inv(inv: Vec<usize>) -> Result<Perm, InvalidPermutationError>

Construct a perm from the vector internally used to represent it.

The format taken by this method is actually the inverse of the format accepted by from_vec. If the kth element of the permutation vector is value, then applying the permutation will push the data at index k over to index value. This format is generally trickier to think about, but is superior to the from_vec representation in terms of efficiency.

This performs O(n log n) validation on the data to verify that it satisfies the invariants of Perm.

pub unsafe fn from_raw_inv_unchecked(inv: Vec<usize>) -> Perm

No-op constructor. Still performs checking in debug builds.

Safety

inv must contain every element in (0..inv.len()), or else the behavior is undefined.

pub fn append_mut(&mut self, other: &Perm)

Construct a permutation of length a.len() + b.len().

Mathematically speaking, this computes the “direct sum” of two permutations.

The inserted elements will be shifted by this permutation’s length, so that they operate on an entirely independent set of data from the existing elements.

pub fn random(n: usize) -> Perm

Construct a random permutation of the given length.

pub fn into_vec(self) -> Vec<usize>

Recover the vector representation of the permutation.

See Perm::from_vec for more details about this representation.

This has a runtime cost of O(n), because Perm does not actually store this vector. See Perm::into_raw_inv for a constant-time alternative.

pub fn into_raw_inv(self) -> Vec<usize>

Obtain the vector that is internally used to represent the permutation.

This representation is actually the inverse of the representation produced by Perm::into_vec. See Perm::from_raw_inv for more information.

pub fn inverted(&self) -> Perm

Get the inverse of this permutation.

pub fn shift_right(self, amt: usize) -> Self

Compose with the permutation that shifts elements forward (performing self first)

To construct the shift permutation itself, use Perm::eye(n).shift_right(amt).

pub fn shift_left(self, amt: usize) -> Self

Compose with the permutation that shifts elements backward (performing self first)

To construct the shift permutation itself, use Perm::eye(n).shift_left(amt).

pub fn shift_signed(self, n: isize) -> Self

Compose with the permutation that shifts elements to the right by a signed offset.

pub fn permute_index(&self, i: usize) -> usize

Apply the permutation to an index. O(1).

Calling this on the indices contained in a sparse-format data structure will produce the same indices as if the corresponding dense-format data structure were permuted.

Panics

Panics if i is out of bounds for the permutation length.

pub fn with_outer(&self, slower: &Perm) -> Perm

Construct the outer product of self and slower, with self being the fast (inner) index.

The resulting Perm will permute blocks of size self.len() according to slower, and will permute elements within each block by self.

pub fn with_inner(&self, faster: &Perm) -> Perm

Construct the outer product of self and faster, with self being the slow (outer) index.

pub fn pow_unsigned(&self, exp: u64) -> Perm

Compute the permutation that applies this permutation exp times in a row.

This uses exponentiation by squaring to run in O(log(exp)) time.

pub fn pow_signed(&self, exp: i64) -> Perm

Compute the permutation that applies this permutation exp times in a row.

This version of the function takes a signed value, so that negative values can produce powers of the inverse.

This uses exponentiation by squaring to run in O(log(exp)) time.

impl Perm

pub fn then(&self, other: &Perm) -> Perm

Flipped group operator, which composes left-to-right.

Very simply. a.then(b) == b.of(a). The flipped order can feel more natural when using method syntax, or if you are dealing with matrix equations written in a row-centric formalism.

Additionally, it has a straightforward relation to the group action:

x.permuted_by(a).permuted_by(b) == x.permuted_by(a.then(b))

pub fn of(&self, other: &Perm) -> Perm

Conventional group operator, which composes right-to-left.

Trait Implementations

impl Clone for Perm

fn clone(&self) -> Perm

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Perm

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

Formats the value using the given formatter.

impl Hash for Perm

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl PartialEq for Perm

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

Tests for self and other values to be equal, 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 Permute for Perm

fn permuted_by(self, other: &Perm) -> Perm

impl Eq for Perm

impl StructuralPartialEq for Perm