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.
My initial thoughts:
We first select a card randomly from the 52 cards. That is probability of 1/52. We then select another card from the rest 51 cards. That is probability of 1/51. So on and so forth. Finally we have a particular permutation with probability of 1/52!, which is expected.
My initial codes:
public static List<Integer> shuffle() { Set<Integer> deck = new HashSet<Integer>(); // build a deck of cards for (int i = 0; i < 52; ++i) { deck.add(i + 1); } List<Integer> shuffledDeck = new ArrayList<Integer>(); for (int i = 0; i < 52; ++i) { int card; do { card = new Random().nextInt(52) + 1; } while (!deck.contains(card)); deck.remove(card); shuffledDeck.add(card); } return shuffledDeck; }Solution:
Let’s start with a brute force approach: we could randomly selecting items and put them into a new array. We must make sure that we don’t pick the same item twice though by somehow marking the node as dead.Array: [1] [2] [3] [4] [5] Randomly select 4: [4] [?] [?] [?] [?] Mark element as dead: [1] [2] [3] [X] [5]The tricky part is, how do we mark [4] as dead such that we prevent that element from being picked again? One way to do it is to swap the now-dead [4] with the first element in the array:
Array: [1] [2] [3] [4] [5] Randomly select 4: [4] [?] [?] [?] [?] Swap dead element: [X] [2] [3] [1] [5] Array: [X] [2] [3] [1] [5] Randomly select 3: [4] [3] [?] [?] [?] Swap dead element: [X] [X] [2] [1] [5]By doing it this way, it’s much easier for the algorithm to “know”” that the first k elements are dead than that the third, fourth, nineth, etc elements are dead. We can also optimize this by merging the shuffled array and the original array:
Randomly select 4: [4] [2] [3] [1] [5] Randomly select 3: [4] [3] [2] [1] [5]This is an easy algorithm to implement iteratively:
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; } }
Gayle Laakmann McDowell
May 29, 2012 @ 01:19:38
Hi Runhe,
I’ve been following your blog for a few months now, and I’ve noticed that while some of the posts are just your attempts at solving the problems, others actually re-type the book’s solutions.
Could you please:
(1) Remove the Cracking the Coding Interview tag on the posts
(2) Refrain from re-posting the book’s solution (which is in fact a violation of copyright law).
Thanks!
Gayle