Use the file Shuffler.java, found below, to implement the perfect shuffle and the efficient selection shuffle methods as described in the Exploration section, also below, of this activity. You will be shuffling arrays of integers. Shuffler.java also provides a main method that calls the shuffling methods. Execute the mainmethod and inspect the output to see how well each shuffle method actually randomizes the array elements. You should execute main with different values of SHUFFLE_COUNTand VALUE_COUNT. Note: this is java! Thank you!

Exploration:

We now consider the shuffling of a deck, that is, the permutation of its cards into a random-looking sequence. A requirement of the shuffling procedure is that any particular permutation has just as much chance of occurring as any other. We will be using the Math.random method to generate random numbers to produce these permutations.

Several ideas for designing a shuffling method come to mind. We will consider two:

Perfect Shuffle

Card players often shuffle by splitting the deck in half and then interleaving the two half-decks, as shown below.

This procedure is called a perfect shuffle if the interleaving alternates between the two half-decks. Unfortunately, the perfect shuffle comes nowhere near generating all possible deck permutations. In fact, eight shuffles of a 52-card deck return the deck to its original state!

Shuffler Class:

/** * This class provides a convenient way to test shuffling methods. */ public class Shuffler {

/** * The number of consecutive shuffle steps to be performed in each call * to each sorting procedure. */ private static final int SHUFFLE_COUNT = 1;

/** * The number of values to shuffle. */ private static final int VALUE_COUNT = 4;

/** * Tests shuffling methods. * @param args is not used. */ public static void main(String[] args) { System.out.println("Results of " + SHUFFLE_COUNT + " consecutive perfect shuffles:"); int[] values1 = new int[VALUE_COUNT]; for (int i = 0; i < values1.length; i++) { values1[i] = i; } for (int j = 1; j <= SHUFFLE_COUNT; j++) { perfectShuffle(values1); System.out.print(" " + j + ":"); for (int k = 0; k < values1.length; k++) { System.out.print(" " + values1[k]); } System.out.println(); } System.out.println();

System.out.println("Results of " + SHUFFLE_COUNT + " consecutive efficient selection shuffles:"); int[] values2 = new int[VALUE_COUNT]; for (int i = 0; i < values2.length; i++) { values2[i] = i; } for (int j = 1; j <= SHUFFLE_COUNT; j++) { selectionShuffle(values2); System.out.print(" " + j + ":"); for (int k = 0; k < values2.length; k++) { System.out.print(" " + values2[k]); } System.out.println(); } System.out.println(); }

/** * Apply a "perfect shuffle" to the argument. * The perfect shuffle algorithm splits the deck in half, then interleaves * the cards in one half with the cards in the other. * @param values is an array of integers simulating cards to be shuffled. */ public static void perfectShuffle(int[] values) { /* *** TO BE IMPLEMENTED IN ACTIVITY 3 *** */ }

/** * Apply an "efficient selection shuffle" to the argument. * The selection shuffle algorithm conceptually maintains two sequences * of cards: the selected cards (initially empty) and the not-yet-selected * cards (initially the entire deck). It repeatedly does the following until * all cards have been selected: randomly remove a card from those not yet * selected and add it to the selected cards. * An efficient version of this algorithm makes use of arrays to avoid * searching for an as-yet-unselected card. * @param values is an array of integers simulating cards to be shuffled. */ public static void selectionShuffle(int[] values) { /* *** TO BE IMPLEMENTED IN ACTIVITY 3 *** */ } }