We wish to develop a computer program (in Matlab), say permvec, which generates a random permutation of the vector (1, 2, ... ,N), where N is an integer supplied by the user of the program.

Matlab already has such a function built in to accomplish this, called randperm(n). It just executes the statement [ignore,p] =

sort(rand(1,n)); to return vector p. To understand this clever method, read the help file on the sort function. This is certainly not the fastest way to construct a random permutation because of the relatively high cost of sorting.

However, it might be the fastest way in Matlab, because the sort function, like many functions and matrix operations, are internal, pre-compiled routines which were originally written in a low-level language such as C or assembler. The Matlab programs we write do not get compiled to machine code, but are interpreted as they are executed, and so run demonstrably slower in comparison.5 Consider the following approach to this problem. It uses the built-in function unidrnd(N) to generate a random integer between 1 and N.

The problem with the code is that we do not ensure that no duplicates occur in the output vector. One way of fixing things is to remove each value from a ‘source vector’ as it is chosen, and then pick only values from the remaining elements of this source vector. Listing 1.2 below shows the implementation of this, in which x is the source vector and, after each iteration in the for loop, the chosen element of x is removed. Notice that random value p is no longer the actual element of output vector, but rather the index into the source array.

(a) A completely different way of accomplishing this is to set up a for loop from 1 to N which exchanges each element in turn with a randomly chosen element from the vector. Write a program which accomplishes this. If the

algorithm works, then we should get approximately the same number of occurrences of the N elements in each of the N positions. To check this, for a given value of N, run the program many times (say 1000), keeping track of the output. From the output, tabulate how many times each of the numbers 1 through N has occurred in each of the N positions.

(b) Now create a program which delivers a random permutation vector as before, but also ensures that there is no overlap with the original vector (1, 2, ... ,N). In other words, if position i contains the number i, then there is overlap.

function y permvec (N) % first attempt. which does NOT work! y zeros (N. 1): for i=1:N y(i) unidrnd (N) : end