Monday, May 2, 2016

Deck Shuffling (algorithm to randomly reorder)



                                         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

The bounds are inclusive, ie [2,5], and min must be less than max in the above example.

No comments:

Post a Comment