Prelab 8: Shuffling

In Lab 8 you will be working with arrays and images. You will design and implement a subroutine to shuffle an array of Strings. By shuffle, we mean that all possible orderings are equally likely.

We create an array of Strings named myPictures as follows:

The length of the array is given by size. The String elements in the myPictures array will correspond to the filenames of JPEG pictures.

Example: Suppose the array myPictures is given by

The array is of length 7. The individual array elements are indexed by

We can "visualize" the myPictures array as follows:

In Lab 8 the myPictures array will contain all the CPS1 student picture .jpg files.

Random Numbers

In order to shuffle, you first need to learn how to create a random number. To create a (pseudo) random integer in the range [0,n) you can use the Random class:

Random gen = new Random() creates a new random number generator gen. The code randIndex = gen.nextInt(n) assigns to randIndex a pseudorandom, uniformly distributed integer value between 0 (inclusive) and n (exclusive), drawn from the random number generator gen's sequence. Inclusive means that the integer value 0 can be generated, while exclusive means the integer value n cannot.

We will provide you with the subroutine RandBetween which returns a random integer between low and high inclusive:

For example,

randIndex = RandBetween(0,4);

will assign to randIndex either 0, 1, 2, 3 or 4 with equal probability.

Problem 1: Write Java code to set the value of a variable x to a random number between 1 and 100 inclusive using the RandBetween subroutine.

Swapping

Suppose we want to swap the array elements myPictures[2] and myPictures[6]. That is, we want the array to "look like" this:

Problem 2: The following code will not correctly swap two elements of an array.

Problem 3: Write code to correctly swap two elements of an array. (Hint: Use a temporary variable.)

Shuffling

The shuffling algorithm systematically rearranges an array of size n by swapping unshuffled elements, beginning with the first element in the array. At each iteration, the element at index k is swapped with an element randomly selected from the range [k,n-1]. At the first iteration we swap the first element in the array, so initially k=0, and the range of unshuffled elements is [0,n-1]. At the second iteration, the element at index 0 is already shuffled, k is incremented to 1, and the range of unshuffled elements is [0,n-1]. This process is continued until k=n-1.

Shuffling algorithm animation

For example, suppose we are given the myPictures array to shuffle.

Unshuffled array:

k=0: Randomly select an index in the range [0,6]. Suppose we choose 4. Then we swap myPictures[0] and myPictures[4].

k=1: Randomly select an index in the range [1,6]. Suppose we choose 5. Swap myPictures[1] and myPictures[5].

k=2: Randomly select an index in the range [2,6]. Suppose we choose 4. Swap myPictures[2] and myPictures[4].

k=3: Randomly select an index in the range [3,6]. Suppose we choose 3. This is a valid swap! Swap myPictures[3] and myPictures[3].

k=4: Randomly select an index in the range [4,6]. Suppose we choose 6. Swap myPictures[4] and myPictures[6].

k=5: Randomly select an index in the range [5,6]. Suppose we choose 6. Swap myPictures[5] and myPictures[6].

k=6: Done! The array is shuffled.

Problem 4: How many swaps are required to shuffle an array n elements, where n is some positive integer? Your expression should be in terms of n.

Problem 5: An array of two elements can be shuffled in only two ways: the ordering is either preserved or the array elements are reversed. How many ways can we shuffle an array of three elements? What about four elements?

Problem 6: How many ways can we shuffle an array of n elements, where n is some positive integer? Your expression should be in terms of n.

Pictures

If your picture is not there, notify your Lab TAs prior to your Lab section so we can take your picture. Make sure to check in the unknown directory and also that the file with your name in fact contains a picture of you and not someone else. You can also provide your own picture, but it must be of dimension 320x240 and in JPEG format with a .jpg file extension. If you want to replace your CPS1 picture and have one of the correct size to substitute, you may send it to your Lab TAs.