Massive Algorithms: Shuffle Cards - Cracking the coding interview--Q20.2

Cracking the coding interview--Q20.2
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!)。假设已经给你一个完美的随机数发生器。

https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2017.%20Hard/Q17_02_Shuffle/Question.java

We would first shuffle the first n - 1 elements. Then, we would take the nth element and randomly swap it with an element in the array.

/* Random number between lower and higher, inclusive*/
int rand(int lower, int higher) {
return lower + (int)(Math.random() * (higher - lower + l));
}

int[] shuffleArrayRecursively(int[] cards, int i) {
if (i == 0) return cards;

shuffleArrayRecursively(cards, i - 1); // Shuffle earlier part
int k = rand(0, i); // Pick random index to swap with

/* Swap element k and i */
int temp= cards[k];
cards(k] cards(i];
cards[i) = temp;

/* Return shuffled array*/
return cards;
}

public static void shuffleArrayIteratively(int[] cards) {
for (int i = 0; i < cards.length; i++) {
int k = rand(0, i);
int temp = cards[k];
cards[k] = cards[i];
cards[i] = temp;
}
}

解答

这是一道非常有名的面试题，及非常有名的算法——随机洗牌算法。
最直观的思路是什么？很简单，每次从牌堆中随机地拿一张出来。那么，第一次拿有52种可能，拿完后剩下51张；第二次拿有51种可能，第三次拿有50种可能， …，一直这样随机地拿下去直到拿完最后1张，我们就从52!种可能中取出了一种排列，这个排列对应的概率是1/(52!)，正好是题目所要求的。
接下来的问题是，如何写代码去实现上面的算法？假设扑克牌是一个52维的数组cards，我们要做的就是从这个数组中随机取一个元素，然后在剩下的元素里再随机取一个元素… 这里涉及到一个问题，就是每次取完元素后，我们就不会让这个元素参与下一次的选取。这个要怎么做呢。
我们先假设一个5维数组：1，2，3，4，5。如果第1次随机取到的数是4，那么我们希望参与第2次随机选取的只有1，2，3，5。既然4已经不用，我们可以把它和1交换，第2次就只需要从后面4位(2,3,1,5)中随机选取即可。同理，第2次随机选取的元素和数组中第2个元素交换，然后再从后面3个元素中随机选取元素，依次类推。

void Swap(int &a, int &b){// 有可能swap同一变量，不能用异或版本
    int t = a;
    a = b;
    b = t;
}
void RandomShuffle(int a[], int n){
    for(int i=0; i<n; ++i){
        int j = rand() % (n-i) + i;// 产生i到n-1间的随机数
        Swap(a[i], a[j]);
    }
}
int main(){
    srand((unsigned)time(0));
    int n = 9;
    int a[] = {
        1, 2, 3, 4, 5, 6, 7, 8, 9
    };
    RandomShuffle(a, n);
    for(int i=0; i<n; ++i)
        cout<<a[i]<<endl;
    return 0;
}

http://coolshell.cn/articles/8593.html
如何测试洗牌程序
Fisher_Yates算法

void ShuffleArray_Fisher_Yates(char* arr, int len)

{

    int i = len, j;

    char temp;

    if ( i == 0 ) return;

    while ( --i ) {

        j = rand() % (i+1);

        temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

}

}

我们有个随机函数rand()返回1到10中的一个数，如果够随机的话，每个数返回的概率都应该是一样的，也就是说每个数都应该有10分之1的概率会被返回。

一到概率问题，我们只有一个方法来做测试，那就是用统计的方式。也就是说，你调用rand()函数100次，其中，每个数出现的次数大约都在10次左右。（注意：我用了左右，这说明概率并不是很准确的）不应该有一个数出现了15次以上，另一个在5次以下，要是这样的话，这个函数就是错的。

举一反三，测试洗牌程序也一样，需要通过概率的方式来做统计，是不是每张牌出现在第一个位置的次数都是差不多的。

其实，以上的测试只是测试了牌在各个位置的概率。这个还不足够好。因为还可能会现在有Patten的情况。如：每次洗牌出来的都是一个循环顺序数组。这完全可以满足我上面的测试条件。但是那明显是错的。所以，还需要统计每种排列的出现的次数，看看是不是均匀。但是，如果这些排列又是以某种规律出现的呢？看来，这没完没了了。

http://n1b-algo.blogspot.com/2007/12/cards-shuffling-problem.html
A common algorithm problem is Cards Shuffling Problem, which states "how to shuffle a deck of cards randomly" or in more general "how to randomize an array of elements". A naive algorithm for this problem can be:

for i = 0 to N
  r = random (0, N)
  exchange C[i] and C[r]

Assume N=2. We see 4 possible combination of (i,r) namely (0,0), (0,1), (1,0), (1,1), leading to 2^2 outputs (N^N in general). However, card shuffling should only lead to N! permutations. So even though this algorithm looks correct, it is logically incorrect. A small change in the above code makes it correct:

for i = 0 to N
  r = random (i, N)
  exchange C[i] and C[r]

Generating r randomly from between i and N ensures that once a card is swapped to a given i, it's position is fixed. Above algorithm, with iteration on cards in reverse order is Knuth-Fisher-Yates shuffle algorithm.
Read full article from Cracking the coding interview--Q20.2

Shuffle Cards - Cracking the coding interview--Q20.2

解答

Labels

Popular Posts