1 Background

A common problem arising in games and simulations is to generate a random arrangements of integers from 1 to N. For examaple, if you were programming a card game, you might represent the deck of cards as an array of N cards. Then, if you could generate a random permutation of the integers 1 through N, you could use that random list as the order in which to draw cards from the shuffled deck.

There is a very good algorithm for generating random permutations:

// Generate a random permutation of the integers from

// 0 .. n-1, storing the results in array a.

//

void permute (int a[], int n)

{

// Fill the array

for (int i = 0; i < n; i++)

{

a[i] = i;

}

for (int i = 0; i < n; i++)

{

k = rnd(n); // random int from 0 .. n-1

swap(a[i], a[k]);

}

}

Random number generators are always designed to be fast (O(1), certainly, but O(1) with a very low constant). A little thought will show that the above algorithm is therefore O(n), and we could hardly hope for anything faster, since it takes O(n) effort just to fill up the array.

Many people, however, find the above algorithm counter-inutitive. It may appear that elements near the end of the array appear to be likely to be swapped more often, so some people wonder if this algorithm is uniformly random - does each integer have an equal probability of winding up in any slot of the array?

In fact the above algorithm is uniformly random, but it takes a careful look at the underlying mathematics to prove this is true. So some programmers prefer to attack this problem by using other algorithms that are more obviously uniformly random.

In this assignment, you will analyze one such alternative algorithm for generating random permutations. You will then check your analysis by timing the algorithm on a variety of input sets to experimentally determine the average-case behavior. You can then check to see if your theoretical analysis is borne out by the actual timings.

2 The Algorithm

The algorithm in permute.cpp generates permutations by generating a random integer for each position in the array, checking to be sure that the generated number has not already been used. It does this check using the find function in std to search the array for the generated number. If found, it means the number has been used.

3 The Assignment

3.1 Analysis

Use the copy-and-paste method to give an average-case analysis for the permute function in permute.cpp.

Assume that the random number generator used in the algorithm produces truly random numbers, i.e, for any integer j in the range 0 .. RAND_MAX, any given call of rand() has a probability 1/RAND_MAX of returning j.

o The rand() function runs in O(1) time (worst-case and average).

• Show all work!

• Remember that you are doing average case analysis.

  3.2 Experiment

  Check your analysis by running the algorithm on a variety of input sizes and measuring the time it takes.

  The program pdriver.cpp can be used as a driver to execute the permute algorithm. This program expects a pair of command line arguments when run. The first argument is the number of items to permute. The second is the number of times you want to repeat the permutation process.

  For example, if you compile this program to produce an executable named pdriver, then pdriver 50 10

  will generate 10 permutations of 50 elements each.

  Because the purpose of this exercise is to generate timing data rather than to actually work with the algorithm, the generated permutations are not printed. Feel free to add output statements if you want to see the algorithms in action, but remember to remove those statements before proceeding on to the timing steps. (I/O is slow and may distort your timing results.)

If, at some point, you dont ask how the average case behavior differs from the

worst case behavior, youre doing it wrong!