Deck with all suits
Question: Deck Shuffling
Given an array of distinct integers, give an algorithm to randomly reorder the
integers so that each possible reordering is equally likely. In other words, given a
deck of cards, how can you shuffle them such that any permutation of cards is
equally likely?
Good answer: Go through the elements in order, swapping each element with a
random element in the array that does not appear earlier than the element. This
takes O(n) time.
/******************************************************************************
* Compilation: javac Deck.java Execution: java Deck
*
* Deal 52 cards uniformly at random.
*
* % java Deck Ace of Clubs 8 of Diamonds 5 of Diamonds ... 8 of Hearts
*
******************************************************************************/
public class Deck {
public static void main(String[] args) {
String[] suit = { "Clubs", "Diamonds", "Hearts", "Spades" };
String[] rank = { "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack",
"Queen", "King", "Ace" };
// avoid hardwired constants
int SUITS = suit.length;
int RANKS = rank.length;
int N = SUITS * RANKS;
// initialize deck
String[] deck = new String[N];
for (int i = 0; i < RANKS; i++) {
for (int j = 0; j < SUITS; j++) {
deck[SUITS * i + j] = rank[i] + " of " + suit[j];
}
}
// shuffle
for (int i = 0; i < N; i++) {
int r = i + (int) (Math.random() * (N - i));//range:N-i i.e. max=N-1; Min=i; range=N-1-i+1.
String t = deck[r];
deck[r] = deck[i];
deck[i] = t;
}
// print shuffled deck
for (int i = 0; i < N; i++) {
System.out.println(deck[i]);
}
}
}
to understand random number generation:
int randomWithRange(int min, int max)
{
int range = (max - min) + 1;
return (int)(Math.random() * range) + min;
}
Output of randomWithRange(2, 5) 10 times:
5
2
3
3
2
4
4
4
5
4
The bounds are inclusive, ie [2,5], and
min must be less than max in the above example. 

No comments:
Post a Comment