Struct rgsl::types::permutation::Permutation
source · pub struct Permutation { /* private fields */ }Implementations§
source§impl Permutation
impl Permutation
##Permutations in cyclic form
A permutation can be represented in both linear and cyclic notations. The functions described in this section convert between the two forms. The linear notation is an index mapping, and has already been described above. The cyclic notation expresses a permutation as a series of circular rearrangements of groups of elements, or cycles.
For example, under the cycle (1 2 3), 1 is replaced by 2, 2 is replaced by 3 and 3 is replaced by 1 in a circular fashion. Cycles of different sets of elements can be combined independently, for example (1 2 3) (4 5) combines the cycle (1 2 3) with the cycle (4 5), which is an exchange of elements 4 and 5. A cycle of length one represents an element which is unchanged by the permutation and is referred to as a singleton.
It can be shown that every permutation can be decomposed into combinations of cycles. The decomposition is not unique, but can always be rearranged into a standard canonical form by a reordering of elements. The library uses the canonical form defined in Knuth’s Art of Computer Programming (Vol 1, 3rd Ed, 1997) Section 1.3.3, p.178.
The procedure for obtaining the canonical form given by Knuth is,
Write all singleton cycles explicitly Within each cycle, put the smallest number first Order the cycles in decreasing order of the first number in the cycle. For example, the linear representation (2 4 3 0 1) is represented as (1 4) (0 2 3) in canonical form. The permutation corresponds to an exchange of elements 1 and 4, and rotation of elements 0, 2 and 3.
The important property of the canonical form is that it can be reconstructed from the contents of each cycle without the brackets. In addition, by removing the brackets it can be considered as a linear representation of a different permutation. In the example given above the permutation (2 4 3 0 1) would become (1 4 0 2 3). This mapping has many applications in the theory of permutations.
sourcepub fn new(n: usize) -> Option<Permutation>
pub fn new(n: usize) -> Option<Permutation>
This function allocates memory for a new permutation of size n. The permutation is not initialized and its elements are undefined. Use the function gsl_permutation_calloc if you want to create a permutation which is initialized to the identity. A null pointer is returned if insufficient memory is available to create the permutation.
sourcepub fn new_with_init(n: usize) -> Option<Permutation>
pub fn new_with_init(n: usize) -> Option<Permutation>
This function allocates memory for a new permutation of size n and initializes it to the identity. A null pointer is returned if insufficient memory is available to create the permutation.
sourcepub fn init(&mut self)
pub fn init(&mut self)
This function initializes the permutation p to the identity, i.e. (0,1,2,…,n-1).
sourcepub fn copy(&self, dest: &mut Permutation) -> Value
pub fn copy(&self, dest: &mut Permutation) -> Value
This function copies the elements of the permutation src into the permutation dest. The two permutations must have the same size.
sourcepub fn get(&self, i: usize) -> usize
pub fn get(&self, i: usize) -> usize
This function returns the value of the i-th element of the permutation p. If i lies outside the allowed range of 0 to n-1 then the error handler is invoked and 0 is returned.
sourcepub fn swap(&mut self, i: usize, j: usize) -> Value
pub fn swap(&mut self, i: usize, j: usize) -> Value
This function exchanges the i-th and j-th elements of the permutation p.
sourcepub fn data<'r>(&'r mut self) -> &'r mut [usize]
pub fn data<'r>(&'r mut self) -> &'r mut [usize]
This function returns a pointer to the array of elements in the permutation p.
sourcepub fn is_valid(&self) -> bool
pub fn is_valid(&self) -> bool
This function checks that the permutation p is valid. The n elements should contain each of the numbers 0 to n-1 once and only once.
sourcepub fn inverse(&self, inv: &mut Permutation) -> Value
pub fn inverse(&self, inv: &mut Permutation) -> Value
This function computes the inverse of the permutation p, storing the result in inv.
sourcepub fn next(&mut self) -> Value
pub fn next(&mut self) -> Value
This function advances the permutation p to the next permutation in lexicographic order and returns GSL_SUCCESS. If no further permutations are available it returns GSL_FAILURE and leaves p unmodified. Starting with the identity permutation and repeatedly applying this function will iterate through all possible permutations of a given order.
sourcepub fn prev(&mut self) -> Value
pub fn prev(&mut self) -> Value
This function steps backwards from the permutation p to the previous permutation in lexicographic order, returning GSL_SUCCESS. If no previous permutation is available it returns GSL_FAILURE and leaves p unmodified.
sourcepub fn permute(&mut self, data: &mut [f64], stride: usize) -> Value
pub fn permute(&mut self, data: &mut [f64], stride: usize) -> Value
This function applies the permutation to the array data of size n with stride stride.
sourcepub fn permute_inverse(&mut self, data: &mut [f64], stride: usize) -> Value
pub fn permute_inverse(&mut self, data: &mut [f64], stride: usize) -> Value
This function applies the inverse of the permutation p to the array data of size n with stride stride.
sourcepub fn permute_vector(&mut self, v: &mut VectorF64) -> Value
pub fn permute_vector(&mut self, v: &mut VectorF64) -> Value
This function applies the permutation p to the elements of the vector v, considered as a row-vector acted on by a permutation matrix from the right, v’ = v P. The j-th column of the permutation matrix P is given by the p_j-th column of the identity matrix. The permutation p and the vector v must have the same length.
sourcepub fn permute_vector_inverse(&self, v: &mut VectorF64) -> Value
pub fn permute_vector_inverse(&self, v: &mut VectorF64) -> Value
This function applies the inverse of the permutation p to the elements of the vector v, considered as a row-vector acted on by an inverse permutation matrix from the right, v’ = v P^T. Note that for permutation matrices the inverse is the same as the transpose. The j-th column of the permutation matrix P is given by the p_j-th column of the identity matrix. The permutation p and the vector v must have the same length.
sourcepub fn mul(&mut self, pa: &Permutation, pb: &Permutation) -> Value
pub fn mul(&mut self, pa: &Permutation, pb: &Permutation) -> Value
This function combines the two permutations pa and pb into a single permutation p, where p = pa * pb. The permutation p is equivalent to applying pb first and then pa.
sourcepub fn linear_to_canonical(&self, q: &mut Permutation) -> Value
pub fn linear_to_canonical(&self, q: &mut Permutation) -> Value
This function computes the canonical form of the permutation self and stores it in the output argument q.
sourcepub fn canonical_to_linear(&self, p: &mut Permutation) -> Value
pub fn canonical_to_linear(&self, p: &mut Permutation) -> Value
This function converts the self permutation in canonical form back into linear form storing it in the output argument p.
sourcepub fn inversions(&self) -> usize
pub fn inversions(&self) -> usize
This function counts the number of inversions in the self permutation. An inversion is any pair of elements that are not in order. For example, the permutation 2031 has three inversions, corresponding to the pairs (2,0) (2,1) and (3,1). The identity permutation has no inversions.
sourcepub fn linear_cycles(&self) -> usize
pub fn linear_cycles(&self) -> usize
This function counts the number of cycles in the self permutation, given in linear form.
sourcepub fn canonical_cycles(&self) -> usize
pub fn canonical_cycles(&self) -> usize
This function counts the number of cycles in the self permutation, given in canonical form.