洗牌算法是一种非常巧妙但又很好理解的算法
用于从m个对象里随机取出n个不重复的对象（n<m）
先来思考一个简单的问题，从0-99里面随机选取一个正整数怎么做，Math.random()*100搞定
那么我有一个长度为100的数组，存了100个不重复的元素，需要从中随机选取50个不能重复的元素该怎么做？Math.random()*100来50次，按下标取到50个元素。但是要求不能重复呀，所以每随机一次都要去判断这个数字是否已经出现过，直到这个数字没有出现过为止。这显然太麻烦了呀。
那我们不妨换一种思路，如果我们把这个长度为100的数组中的元素随机打乱顺序，就像洗牌一样，然后直接取前50个元素不就好了。
OK，那么怎样算随机打乱顺序？每一个元素出现在任一位置的概率均相等，才算随机打乱顺序。这就用到了洗牌算法。一句话就可以解释：遍历每一个元素，将它和包括自身及之后的所有元素中随机选取的一个元素进行交换，直到遍历够需要的数量为止
比如有一个数组，里面存的{1,2,3,4,5}，我们需要随机取出其中不重复的3个数
- 我们来遍历这个数组，第一个元素是1，假设我们随机到了它跟4这个元素交换为止，数组变为{4,2,3,1,5}。任意一个数在第一位的概率都是1/5
- 继续遍历，第二个元素是2，我们从第2个到第5个这4个元素中随机，假设我们随机到了2本身，那么数组还是{4,2,3,1,5}。这个算法牛逼的地方到了，因为2逃过了第一轮交换，且在第二轮被选中，那么它出现在第二位的概率是4/5*1/4=1/5
- 继续遍历，第三个元素是3，我们从第3个到第5个这3个元素中随机，假设我们随机到了5，数组变为{4,2,5,1,3}。5出现在第三位的概率是4/53/41/3=1/5
- 继续遍历，第4个元素是1，我们从第4个到第5个这2个元素中随机，假设我们随机到了3，数组变为{4,2,5,3,1}。我们要注意，虽然3之前被交换到了第5位，但是它并没有被选中过，只是遍历到了它而被动交换，3出现在第四位的概率是4/53/42/3*1/2=1/5
- 最后剩下的1留在了第5位，1出现在第五位的概率同样也是4/53/42/3*1/2=1/5
我们可以看到，每一个元素出现在任一位置的概率均为1/5。我为了解释这个算法，进行了一轮完整的遍历，在实际应用中，因为我们只要取到不重复的3个数就可以，所以遍历到第3轮结束，拿到{4,2,5}就可以停止了。
再注意一下，这个数组的长度是5，需要随机取3个不重复的数，其实随机取到2个不重复的数以后，剩下的3个数不就是随机的3个数了么？所以我们遍历到第2轮结束，扔掉{4,2},剩下的{3,1,5}同样也满足随机取出不重复的3个数。
代码如下：
import random
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 6 # 取出6个不重复的数字
num = (len(arr) - count) if count > len(arr) / 2 else count
for i in range(0, num):
temp = arr[i]
rand = random.randint(i, len(arr) - 1)
arr[i] = arr[rand]
arr[rand] = temp
result = arr[num:] if count > len(arr) / 2 else arr[:num]
print(result)
