hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
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
57
4216
3
is composed of the cycles
1 5 2 7 3 4 6
(15)
(2734)
(6)
and the vector icycl generated by nag_sort_permute_decompose (m01zc) contains
1 5 2 7 3 4 6
-1 5 -2 7 3 4 -6
In order to rearrange the data according to the specified ranks:
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

References

None.

Parameters

Compulsory Input Parameters

1:     iperm(m2) – int64int32nag_int array
m2, the dimension of the array, must satisfy the constraint 0 < m1m20<m1m2.
Elements m1 to m2 of iperm must contain a permutation of the integers m1 to m2.
2:     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 < m1m20<m1m2.

Optional Input Parameters

1:     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 < m1m20<m1m2.

Input Parameters Omitted from the MATLAB Interface

None.

Output Parameters

1:     iperm(m2) – int64int32nag_int array
Is used as internal workpsace prior to being restored and hence is unchanged.
2:     icycl(m2) – 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 Section [Description].)
3:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
On entry,m2 < 1m2<1,
orm1 < 1m1<1,
orm1 > m2m1>m2.
  ifail = 2ifail=2
Elements m1 to m2 of iperm contain a value outside the range m1 to m2.
  ifail = 3ifail=3
Elements m1 to m2 of iperm contain a repeated value.
If ifail = 2ifail=2 or 33, elements m1 to m2 of iperm do not contain a permutation of the integers m1 to m2.

Accuracy

Not applicable.

Further Comments

None.

Example

function nag_sort_permute_decompose_example
iperm = [int64(12);1;9;2;4;8;11;3;5;6;10;7];
m1 = int64(1);
[ipermOut, icycl, ifail] = nag_sort_permute_decompose(iperm, m1)
 

ipermOut =

                   12
                    1
                    9
                    2
                    4
                    8
                   11
                    3
                    5
                    6
                   10
                    7


icycl =

                   -1
                   12
                    7
                   11
                   10
                    6
                    8
                    3
                    9
                    5
                    4
                    2


ifail =

                    0


function m01zc_example
iperm = [int64(12);1;9;2;4;8;11;3;5;6;10;7];
m1 = int64(1);
[ipermOut, icycl, ifail] = m01zc(iperm, m1)
 

ipermOut =

                   12
                    1
                    9
                    2
                    4
                    8
                   11
                    3
                    5
                    6
                   10
                    7


icycl =

                   -1
                   12
                    7
                   11
                   10
                    6
                    8
                    3
                    9
                    5
                    4
                    2


ifail =

                    0



PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013