> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/simulation/probability.md).

# 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](http://massivealgorithms.blogspot.com/2015/07/shuffle-cards-cracking-coding-interview.html)

```java
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

```java
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;        
}
```