IN JAVA. Suppose that the initial contents of the values array in Shuffler.java
ID: 3686449 • Letter: I
Question
IN JAVA. Suppose that the initial contents of the values array in Shuffler.java are {1, 2, 3, 4}. For what sequence of random integers would the efficient selection shuffle change values to contain{4, 3, 2, 1}? I AM LOOKING FOR A SEQUENCE OF NUMBERS.
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 *** */
}
}
Explanation / Answer
Shuffler.java
public class Shuffler {
private static final int SHUFFLE_COUNT = 5;
private static final int VALUE_COUNT = 10;
/**
* 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++) {
values1 = 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++) {
values2 = 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 int[] perfectShuffle(int[] values) {
int[] tVal = new int[values.length];
int c = 0;
for (int i = 0; i < (values.length + 1) / 2; i++) {
tVal[c] = values[i];
c += 2;
}
c = 1;
for (int i = (values.length + 1) / 2; i < values.length; i++) {
tVal[c] = values[i];
c += 2;
}
return tVal;
}
public static int[] selectionShuffle(int[] values) {
for (int i = values.length - 1; i > 0; i--) {
int t = (int) Math.round(Math.random() * i);
int tmp = values[i];
values[i] = values[t];
values[t] = tmp;
}
return values;
}
}
sample output
Results of 5 consecutive perfect shuffles:
1: 0 5 1 6 2 7 3 8 4 9
2: 0 7 5 3 1 8 6 4 2 9
3: 0 8 7 6 5 4 3 2 1 9
4: 0 4 8 3 7 2 6 1 5 9
5: 0 2 4 6 8 1 3 5 7 9
Results of 5 consecutive efficient selection shuffles:
1: 2 6 0 9 4 3 8 1 5 7
2: 9 3 2 8 1 4 6 7 0 5
3: 9 1 2 8 6 3 5 4 0 7
4: 5 7 4 3 2 6 1 9 0 8
5: 0 4 2 1 3 8 9 6 5 7