Embedded Files
Introduction
Introduction
Think about how you shuffle a deck by hand. How well do you think it randomizes the order of the deck?
Exploration
Exploration
We're going to work on creating permutations of a deck's cards that appear to be random sequences. It is important that each permutation has an equal chance of occurring. You'll use Math.random to get random-esque numbers.
Here are a few possible ways to shuffle:
Exercises
Exercises
- Copy the code below into a new class called Shuffler.
- Execute the main method and review what happens. Try out different values of SHUFFLE_COUNT and VALUE_COUNT.
- Write a static method named flip that simulates a flip of a weighted coin by returning "heads" or "tails." Make it twice as likely to return heads.
- Write a static method named arePermutations that, given two int arrays of the same length, but no duplicate elements, returns true if one array is a permutation of the other, and false otherwise.
- Implement the perfect shuffle strategy in the perfectShuffle() method OR the selection shuffle strategy in the selectionShuffle() method OR your own shuffle strategy that you invent in the myShuffle() method.
Shuffler.java
Shuffler.java
/** * 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 *** */ } /** * Apply your own shuffle strategy to the argument. * @param values is an array of integers simulating cards to be shuffled. */ public static void myShuffle(int[] values) { /* *** TO BE IMPLEMENTED IN ACTIVITY 3 *** */ }}Report abuse