Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. - From Cracking the Code Interview
public static void shuffleArray(int[] cards) {
int temp, index;
for (int i = 0; i < cards.length; i++){
index = (int) (Math.random() * (cards.length - i)) + i;
temp = cards[i];
cards[i] = cards[index];
cards[index] = temp;
}
}
Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen. - From Cracking the Code Interview
public static int rand(int lower, int higher) {
return lower + (int)(Math.random() * (higher - lower + 1));
}
/* pick M elements from original array. Clone original array so that
* we don’t destroy the input. */
public static int[] pickMRandomly(int[] original, int m) {
int[] subset = new int[m];
int[] array = original.clone();
for (int j = 0; j < m; j++) {
int index = rand(j, array.length - 1);
subset[j] = array[index];
array[index] = array[j]; // array[j] is now “dead”
}
return subset;
}
public static int[] pickMRecursively(int[] original, int m, int i) {
if (i + 1 < m) { // Not enough elements
return null;
} else if (i + 1 == m) { // Base case -- copy first m elements into array
int[] set = new int[m];
for (int k = 0; k < m; k++) {
set[k] = original[k];
}
return set;
} else {
int[] set = pickMRecursively(original, m, i - 1);
int k = rand(0, i);
if (k < m) {
set[k] = original[i];
}
return set;
}
}
/* pick M elements from original array.*/
public static int[] pickMIteratively(int[] original, int m) {
int[] subset = new int[m];
/* Fill in subset array with first part of original array */
for (int i = 0; i < m ; i++) {
subset[i] = original[i];
}
/* Go through rest of original array. */
for (int i = m; i < original.length; i++) {
int k = rand(0, i);
if (k < m) {
subset[k] = original[i];
}
}
return subset;
}
public static void shuffleArray(int[] cards) {
int temp, index;
for (int i = 0; i < cards.length; i++){
index = (int) (Math.random() * (cards.length - i)) + i;
temp = cards[i];
cards[i] = cards[index];
cards[index] = temp;
}
}
Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen. - From Cracking the Code Interview
public static int rand(int lower, int higher) {
return lower + (int)(Math.random() * (higher - lower + 1));
}
/* pick M elements from original array. Clone original array so that
* we don’t destroy the input. */
public static int[] pickMRandomly(int[] original, int m) {
int[] subset = new int[m];
int[] array = original.clone();
for (int j = 0; j < m; j++) {
int index = rand(j, array.length - 1);
subset[j] = array[index];
array[index] = array[j]; // array[j] is now “dead”
}
return subset;
}
We can first pull a random set of size m from the first n - 1 elements. Then, we just need to decide if
array [ n] should be inserted into our subset (which would require pulling out a random element from it).
An easy way to do this is to pick a random number k from 0 through n. If k < m, then insert array[ n] into subset [ k]. This will both "fairly" (i.e., with proportional probability) insert array[ n] into the subset and "fairly" remove a random element from the subset.
/* pick M elements from original array, using only elements 0 through i (inclusive).*/public static int[] pickMRecursively(int[] original, int m, int i) {
if (i + 1 < m) { // Not enough elements
return null;
} else if (i + 1 == m) { // Base case -- copy first m elements into array
int[] set = new int[m];
for (int k = 0; k < m; k++) {
set[k] = original[k];
}
return set;
} else {
int[] set = pickMRecursively(original, m, i - 1);
int k = rand(0, i);
if (k < m) {
set[k] = original[i];
}
return set;
}
}
/* pick M elements from original array.*/
public static int[] pickMIteratively(int[] original, int m) {
int[] subset = new int[m];
/* Fill in subset array with first part of original array */
for (int i = 0; i < m ; i++) {
subset[i] = original[i];
}
/* Go through rest of original array. */
for (int i = m; i < original.length; i++) {
int k = rand(0, i);
if (k < m) {
subset[k] = original[i];
}
}
return subset;
}
