NAG Library Function Document

nag_ran_permut_vec (g05ehc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

nag_ran_permut_vec (g05ehc) performs a pseudorandom permutation of a vector of integers.

2 Specification

#include <nag.h>

#include <nagg05.h>

void	nag_ran_permut_vec (Integer index[], Integer n, NagError *fail)

3 Description

nag_ran_permut_vec (g05ehc) generates a single pseudorandom permutation of the elements of index without inspecting their values. Each of the

n

! possible permutations of the

n

values may be regarded as being equiprobable.

4 References

Kendall M G and Stuart A (1969) The Advanced Theory of Statistics (Volume 1) (3rd Edition) Griffin

Knuth D E (1981) The Art of Computer Programming (Volume 2) (2nd Edition) Addison–Wesley

5 Arguments

1: index[n] – IntegerInput/Output: On entry: the $n$ integer values to be permuted.

On exit: the $n$ permuted integer values.
2: n – IntegerInput: On entry: the number of values to be permuted.
Constraint: $n \geq 1$ .
3: fail – NagError *Input/Output: The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_INT_ARG_LT: On entry, $n = 〈value〉$ .
Constraint: $n \geq 1$ .

7 Accuracy

Not applicable.

8 Further Comments

It should be noted that if

n

is 20 or more it is theoretically impossible to generate all

n

! permutations as

n

! exceeds the cycle length of the internal random number generator. The time taken by the function is of order

n

. In order to permute other kinds of objects (i.e., vectors, or matrices of higher dimensions), the following technique may be used:

(a)	Set $index [i - 1] = i$ , for $i = 1, 2, \dots, n$ (where $n$ is the number of objects)
(b)	Use nag_ran_permut_vec (g05ehc) to permute index
(c)	Use the contents of index as a set of indices to access the relevant object.

In order to divide pseudorandomly an array of

n

objects (obj_array

[n]

) into

k

subgroups of chosen sizes

S_{1}, S_{2}, \dots, S_{k}

a similar procedure may be used. For the first

S_{1}

, elements of index set

index [i] = 1, i = 0 \dots S_{1} - 1

, for the next

S_{2}

elements of index set

index [S_{1} + i] = 2, i = 0 \dots S_{2} - 1

, for size

S_{j}

set

index [S_{1} + S_{2} + \dots + S_{j - 1} + i] = j

, for

i = 0 \dots S_{j} - 1

, etc. Permute index using nag_ran_permut_vec (g05ehc) and then, if

index [i] = j

, obj_array

[i]

is to be included in the

j

th subgroup.

9 Example

A vector containing 0 and the first 7 positive integers in ascending order is permuted and the permutation is printed. This is repeated a total of 10 times.