Probability

Shuffle Card

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

抽出的52!組合是同機率 1/52!

• 抽的數字從array後面選，選完之後swap,之後每次選都是沒抽過的數字

link

void shuffleCard(int[] cards, int n){
    for(int i=0; i<cards.length; i++){
        int j=rand.nextInt(i, n);
        swap(cards[i], cards[j]);
    }
}

Select a random number from stream with equal probability

Given a stream of numbers, generate a random number from the stream. You are allowed to use only O(1) space and the probability of each number is 1/n, n is the number seen so far

• init a count as 0, means the number has been seen so far

• for each number x, generate ran number 0 to count-1. If ran is count-1, set ans to ran

• 對於每一個數字而言, 當下被選中的機率是1/n

• 之後每次iteration, 若n2沒被選中 (n-1)/n, 保留的數字可能是n-1中的一個 1/(n-1) => (n-1)/n * 1/(n-1) = 1/n => 機率仍然是 1/n

int count=0;
int ans=0;

int selectRandom(int x){
    count++;
    if(count==1) return x;

        Random ran = new Random();
        // generate a number for 0 to count-1
        int n = nextInt(count);
        if(n == count-1) ans = x
        return x;        
}