Shuffle Array(Hard)
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!)。假设已经给你一个完美的随机数发生器。
解题思路
这是一道非常有名的面试题，及非常有名的算法——随机洗牌算法。
最直观的思路是什么？很简单，每次从牌堆中随机地拿一张出来。那么， 第一次拿有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个元素中随机选取元素， 依次类推。
//The bounds are inclusive, ie [2,5], and min must
//be less than max in the above example.
int randomWithRange(int min, int max){
int range = (max - min) + 1;
return (int)(Math.random() * range) + min;
}
public static void shuffleArrayInteratively(int[] cards) {
for (int i = 0; i < cards.length; i++) {
//产生i到n-1间的随机数
int k = randomWithRange(i, cards.length-1);
int temp = cards[k];
cards[k] = cards[i];
cards[i] = temp;
}
}