Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sort_permute_decompose (m01zc)

## Purpose

nag_sort_permute_decompose (m01zc) decomposes a permutation into cycles, as an aid to reordering ranked data.

## Syntax

[iperm, icycl, ifail] = m01zc(iperm, m1, 'm2', m2)
[iperm, icycl, ifail] = nag_sort_permute_decompose(iperm, m1, 'm2', m2)

## Description

nag_sort_permute_decompose (m01zc) 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 M01E reordering functions.) Given a vector IRANK which specifies the ranks of the data (as generated by the M01D functions), nag_sort_permute_decompose (m01zc) 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
 $5 7 4 2 1 6 3$
is composed of the cycles
 $1 5 2 7 3 4 6$
and the vector icycl generated by nag_sort_permute_decompose (m01zc) contains
 $-1 5 -2 7 3 4 -6$
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 code:
```  for k=m1:m2
ii = icycl(k);
if (ii < 0)
jj = -ii;
else
% swap items ii and jj
end
end```

None.

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{iperm}\left({\mathbf{m2}}\right)$int64int32nag_int array
Elements m1 to m2 of iperm must contain a permutation of the integers m1 to m2.
2:     $\mathrm{m1}$int64int32nag_int scalar
m1 and m2 must specify the range of elements used in the array iperm and the range of values in the permutation, as specified under iperm.
Constraint: $0<{\mathbf{m1}}\le {\mathbf{m2}}$.

### Optional Input Parameters

1:     $\mathrm{m2}$int64int32nag_int scalar
Default: the dimension of the array iperm.
m1 and m2 must specify the range of elements used in the array iperm and the range of values in the permutation, as specified under iperm.
Constraint: $0<{\mathbf{m1}}\le {\mathbf{m2}}$.

### Output Parameters

1:     $\mathrm{iperm}\left({\mathbf{m2}}\right)$int64int32nag_int array
Is used as internal workpsace prior to being restored and hence is unchanged.
2:     $\mathrm{icycl}\left({\mathbf{m2}}\right)$int64int32nag_int array
Elements m1 to m2 of icycl contain a representation of the permutation as a list of cycles, with the first integer in each cycle negated. (See Description.)
3:     $\mathrm{ifail}$int64int32nag_int scalar
${\mathbf{ifail}}={\mathbf{0}}$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

Errors or warnings detected by the function:
${\mathbf{ifail}}=1$
 On entry, ${\mathbf{m2}}<1$, or ${\mathbf{m1}}<1$, or ${\mathbf{m1}}>{\mathbf{m2}}$.
${\mathbf{ifail}}=2$
Elements m1 to m2 of iperm contain a value outside the range m1 to m2.
${\mathbf{ifail}}=3$
Elements m1 to m2 of iperm contain a repeated value.
If ${\mathbf{ifail}}={\mathbf{2}}$ or ${\mathbf{3}}$, elements m1 to m2 of iperm do not contain a permutation of the integers m1 to m2.
${\mathbf{ifail}}=-99$
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

Not applicable.

None.

## Example

This example reads a matrix of real numbers and rearranges its columns so that the elements of the $l$th row are in ascending order. To do this, the program first calls nag_sort_realmat_rank_columns (m01dj) to rank the elements of the $l$th row, and then calls nag_sort_permute_decompose (m01zc) to decompose the rank vector into cycles. It then rearranges the columns using the framework of code suggested in Description. The value of $l$ is read from the data file.
```function m01zc_example

fprintf('m01zc example results\n\n');

rm = [5, 4, 3, 2, 2, 1, 9, 4, 4, 2, 2, 1;
3, 8, 2, 5, 5, 6, 9, 8, 9, 5, 4, 1;
9, 1, 6, 1, 2, 4, 8, 1, 2, 2, 6, 2];

m1 = int64(1);
n1 = int64(1);
l = int64(3);
order = 'Ascending';

% Rank by (l-th) third row
[irank, ifail] = m01dj( ...
rm, l, n1, order, 'm2', l);

[irank, icycl, ifail] = m01zc(irank, m1);

[rm] = m01zc_reorder(rm,icycl);

fprintf('Matrix sorted on row %d\n',l);
for i = 1:size(rm,1)
fprintf('%5.1f',rm(i,:));
fprintf('\n');
end

function [rm] = m01zc_reorder(rm,icycl)

for k = 1:size(rm,2)
i = icycl(k);
if i<0
j = -i;
else
% Swap columns i and j
t = rm(:,j);
rm(:,j) = rm(:,i);
rm(:,i) = t;
end
end
```
```m01zc example results

Matrix sorted on row 3
4.0  2.0  4.0  2.0  4.0  2.0  1.0  1.0  3.0  2.0  9.0  5.0
8.0  5.0  8.0  5.0  9.0  5.0  1.0  6.0  2.0  4.0  9.0  3.0
1.0  1.0  1.0  2.0  2.0  2.0  2.0  4.0  6.0  6.0  8.0  9.0
```