nag_ran_permut_vec (g05ehc) (PDF version)
g05 Chapter Contents
g05 Chapter Introduction
NAG C Library Manual

NAG Library Function Document

nag_ran_permut_vec (g05ehc)

+ Contents

    1  Purpose
    7  Accuracy

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:     nIntegerInput
On entry: the number of values to be permuted.
Constraint: n1 .
3:     failNagError *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: n1.

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,,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 , , S k  a similar procedure may be used. For the first S 1 , elements of index set index[i] = 1 , i = 0 S 1 - 1 , for the next S 2  elements of index set index[ S 1 + i ] = 2 , i = 0 S 2 - 1 , for size S j  set index[ S 1 + S 2 + + S j-1 + i ] = j, for i = 0 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.

9.1  Program Text

Program Text (g05ehce.c)

9.2  Program Data

None.

9.3  Program Results

Program Results (g05ehce.r)


nag_ran_permut_vec (g05ehc) (PDF version)
g05 Chapter Contents
g05 Chapter Introduction
NAG C Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2012