naginterfaces.library.sort.permute_​decompose

naginterfaces.library.sort.permute_decompose(iperm, m1)

permute_decompose decomposes a permutation into cycles, as an aid to reordering ranked data.

For full information please refer to the NAG Library document for m01zc

https://support.nag.com/numeric/nl/nagdoc_30.1/flhtml/m01/m01zcf.html

Parameters

ipermint, array-like, shape $\left(\text{m2}\right)$

Elements $m1-1$ to $\text{m2}-1$ of $iperm$ must contain a permutation of the integers $m1$ to $\text{m2}$.

m1int

Note: this argument represents an array index; the value you supply must be base-1 for compatibility with the NAG Engine.

$m1$ and $\text{m2}$ must specify the range of elements used in the array $iperm$ and the range of values in the permutation, as specified under $iperm$.

Returns

ipermint, ndarray, shape $\left(\text{m2}\right)$

Is used as internal workpsace prior to being restored and hence is unchanged.

icyclint, ndarray, shape $\left(\text{m2}\right)$

Elements $m1-1$ to $\text{m2}-1$ of $icycl$ contain a representation of the permutation as a list of cycles, with the first integer in each cycle negated. (See Notes.)

Raises

NagValueError

(errno $1$)

On entry, $m1=⟨value⟩$ and $\text{m2}=⟨value⟩$.

Constraint: $m1\le \text{m2}$.

(errno $1$)

On entry, $m1=⟨value⟩$.

Constraint: $m1\ge 1$.

(errno $1$)

On entry, $\text{m2}=⟨value⟩$.

Constraint: $\text{m2}\ge 1$.

(errno $2$)

$iperm[m1:\text{m2}-1]$ does not contain a permutation of the integers $m1$ to $\text{m2}$. $iperm[I-1]$ contains an out-of-range value: $I=⟨value⟩$, $iperm[I-1]=⟨value⟩$.

(errno $3$)

$iperm[m1:\text{m2}-1]$ does not contain a permutation of the integers $m1$ to $\text{m2}$. $iperm$ contains a repeated value: $⟨value⟩$.

Notes

No equivalent traditional C interface for this routine exists in the NAG Library.

permute_decompose is provided as an aid to reordering arbitrary data structures without using additional storage. However, you should consider carefully whether it is necessary to rearrange yourr data, or whether it would be simpler and more efficient to refer to the data in sorted order using an index vector, or to create a copy of the data in sorted order.

To rearrange data into a different order without using additional storage, the simplest method is to decompose the permutation which specifies the new order into cycles and then to do a cyclic permutation of the data items in each cycle. (This is the method used by the reordering functions realvec_rank_rearrange(), intvec_rank_rearrange(), charvec_rank_rearrange() and cmplxvec_rank_rearrange().) Given a vector IRANK which specifies the ranks of the data (as generated by the functions realvec_rank(), intvec_rank(), charvec_rank(), realmat_rank_rows(), intmat_rank_rows(), realmat_rank_columns(), intmat_rank_columns() and arbitrary_rank()), permute_decompose generates a new vector $icycl$, in which the permutation is represented in its component cycles, with the first element of each cycle negated. For example, the permutation

$$\begin{array}{ccc}\begin{array}{cc}5& 7\end{array}& \begin{array}{cccc}4& 2& 1& 6\end{array}& \begin{array}{c}3\end{array}\end{array}$$

is composed of the cycles

$$\begin{array}{ccc}\left(\begin{array}{cc}1& 5\end{array}\right)& \left(\begin{array}{cccc}2& 7& 3& 4\end{array}\right)& \left(\begin{array}{c}6\end{array}\right)\end{array}$$

and the vector $icycl$ generated by permute_decompose contains

$$\begin{array}{ccccccc}-1& 5& -2& 7& 3& 4& -6\end{array}$$

In order to rearrange the data according to the specified ranks:

item $6$ must be left in place;

items $1$ and $5$ must be interchanged;

items $4$, $2$, $7$ and $3$ must be moved right one place round the cycle.

The complete rearrangement can be achieved by the following logic:

loop for $k=m1$ to $\text{m2}$

set $i=icycl[k-1]$

if $i<0$ then

set $j=-i$

else

swap items $i$ and $j$