2014-08-24
**问题描述：**有n张牌和n个位置，如何让每张牌出现在每个位置的可能性是1/n？
其实，可以把这个算法分成两个目标：
- 目标1：得到的结果看起来是随机的。
- 目标2：某张牌出现在某个位置的可能性是1/n；某个位置上出现某张牌的可能性是1/n。
要解决这个问题，有一点需要注意，牌一定要看成乱序的，牌在开始时候的顺序不应该影响洗牌的结果。
好了，现在我们手中有四张牌：a、b、c、d。
方法1
从n张牌中，随机抽出1张牌，放在位置0；从剩下的牌中随机抽出一张牌，放在位置1，如此循环，直到没有剩下的牌。
ruby实现如下：
# !/usr/bin/env ruby
# coding: UTF-8
# 方法1
def shuffle01(arr)
len = arr.length
arr2 = []
for i in 0..len-1
index = Random.rand(0..arr.length-1)
arr2 << arr[index]
arr.delete_at(index)
end
return arr2
end
arr = ['a', 'b', 'c', 'd']
ret = shuffle01(arr)
p ret
运行几次的结果：
["d", "a", "c", "b"]
["c", "d", "b", "a"]
["a", "d", "c", "b"]
......
这个解法在数学上很容易证明其满足目标1和目标2，也可以使用统计的方式证明其正确性。以牌a为例，记录其在分别位置0、1、2、3出现的次数，若这些次数差不多，就没问题了。 下面测试方法1：
# !/usr/bin/env ruby
# coding: UTF-8
# 测试方法1
class ShuffleTest
def initialize
@count = {'a'=>[0, 0, 0, 0], 'b'=>[0, 0, 0, 0], 'c'=>[0, 0, 0, 0], 'd'=>[0, 0, 0, 0]}
end
def count(arr)
for i in 0...arr.length
@count[arr[i]][i] += 1
end
end
def show_count
return @count
end
end
def shuffle01(arr)
len = arr.length
arr2 = []
for i in 0..len-1
index = Random.rand(0..arr.length-1)
arr2 << arr[index]
arr.delete_at(index)
end
return arr2
end
st = ShuffleTest.new
for x in 0..100_0000
arr = ['a', 'b', 'c', 'd']
ret = shuffle01(arr)
st.count(ret)
end
st.show_count.each do |k, v|
puts k
p v
end
运行结果是：
a
[249240, 250379, 249773, 250609]
b
[249671, 249465, 249983, 250882]
c
[250426, 250659, 249913, 249003]
d
[250664, 249498, 250332, 249507]
这是很令人满意的结果。
改进方法1
在测试时可以发现方法1有一个严重的问题，即每调用一次shuffle01()，arr会被置空，且会生成一新的数组对象arr2。一个比较好的方法是在arr内部进行调整，如下：
# !/usr/bin/env ruby
# coding: UTF-8
# 方法1的改进版
def shuffle01!(arr)
len = arr.length
arr2 = []
for i in 0..len-1
index = Random.rand(i..arr.length-1)
arr[i], arr[index] = arr[index], arr[i]
end
end
arr = ['a', 'b', 'c', 'd']
shuffle01!(arr)
p arr
测试程序：
# !/usr/bin/env ruby
# coding: UTF-8
# 测试方法1的改进版
class ShuffleTest
def initialize
@count = {'a'=>[0, 0, 0, 0], 'b'=>[0, 0, 0, 0], 'c'=>[0, 0, 0, 0], 'd'=>[0, 0, 0, 0]}
end
def test(arr)
for i in 0...arr.length
@count[arr[i]][i] += 1
end
end
def show_count
return @count
end
end
def shuffle01!(arr)
len = arr.length
arr2 = []
for i in 0..len-1
index = Random.rand(i..arr.length-1)
arr[i], arr[index] = arr[index], arr[i]
end
end
arr = ['a', 'b', 'c', 'd']
st = ShuffleTest.new
for x in 0..100_0000
shuffle01!(arr)
st.test(arr)
end
st.show_count.each do |k, v|
puts k
p v
end
某次运行结果如下：
a
[249582, 251038, 249247, 250134]
b
[250064, 249597, 250502, 249838]
c
[249849, 249907, 250344, 249901]
d
[250506, 249459, 249908, 250128]
这个测试程序的运行速度要比方法1的测试程序快一些。
方法2
这个思路和方法1差不多：从n张牌中，随机抽出1张牌，放在位置n-1；从剩下的牌中随机抽出一张牌，放在位置n-2，如此循环，直到没有剩下的牌。该算法同样满足目标1和目标2。
代码：
# !/usr/bin/env ruby
# coding: UTF-8
# 方法2
def shuffle02(arr)
len = arr.length
arr2 = []
for i in 0..len-1
index = Random.rand(0..arr.length-1)
arr2.insert(0, arr[index])
arr.delete_at(index)
end
return arr2
end
arr = ['a', 'b', 'c', 'd']
ret = shuffle02(arr)
p ret
测试：
# !/usr/bin/env ruby
# coding: UTF-8
# 测试方法2
class ShuffleTest
def initialize
@count = {'a'=>[0, 0, 0, 0], 'b'=>[0, 0, 0, 0], 'c'=>[0, 0, 0, 0], 'd'=>[0, 0, 0, 0]}
end
def count(arr)
for i in 0...arr.length
@count[arr[i]][i] += 1
end
end
def show_count
return @count
end
end
def shuffle02(arr)
len = arr.length
arr2 = []
for i in 0..len-1
index = Random.rand(0..arr.length-1)
arr2.insert(0, arr[index])
arr.delete_at(index)
end
return arr2
end
st = ShuffleTest.new
for x in 0..100_0000
arr = ['a', 'b', 'c', 'd']
ret = shuffle02(arr)
st.count(ret)
end
st.show_count.each do |k, v|
puts k
p v
end
测试程序的某次运行结果：
a
[250163, 249683, 249885, 250270]
b
[250047, 249585, 249815, 250554]
c
[249694, 251029, 250102, 249176]
d
[250097, 249704, 250199, 250001]
方法3
把牌最开始的摆放顺序认为是有序的。随机生成两个在0和n-1之间（包括这两个数）的整数，将这两个位置的牌调换swap，如此循环操作n次。 代码如下：
# !/usr/bin/env ruby
# coding: UTF-8
# 方法3
def shuffle03!(arr)
len = arr.length
for i in 0..len-1
index1 = Random.rand(0..len-1)
index2 = Random.rand(0..len-1)
arr[index1], arr[index2] = arr[index2], arr[index1]
end
end
arr = ['a', 'b', 'c', 'd']
shuffle03!(arr)
p arr
测试代码如下：
# !/usr/bin/env ruby
# coding: UTF-8
# 测试方法3
class ShuffleTest
def initialize(seed)
len = seed.length
@count = {}
for i in 0..len-1
@count[seed[i]] = Array.new(len, 0)
end
end
def test(arr)
for i in 0...arr.length
@count[arr[i]][i] += 1
end
end
def show_count
return @count
end
end
def shuffle03!(arr)
len = arr.length
for i in 0..len-1
index1 = Random.rand(0..len-1)
index2 = Random.rand(0..len-1)
arr[index1], arr[index2] = arr[index2], arr[index1]
end
end
arr = ['a', 'b', 'c', 'd']
st = ShuffleTest.new(arr)
for x in 0..100_0000
shuffle03!(arr)
st.test(arr)
end
st.show_count.each do |k, v|
puts k
p v
end
注意，这次把类ShuffleTest修改得更通用了一些。测试程序的某次运行结果如下：
a
[249744, 249342, 250650, 250265]
b
[250820, 249464, 249793, 249924]
c
[250018, 249958, 250620, 249405]
d
[249419, 251237, 248938, 250407]
这个程序自然满足目标1,同时看起来满足目标2,但实际上并不满足目标2。这个需要证明一下（我没什么头绪，在stackoverflow问了下，找到了答案，问题地址是：Is this shuffle algorithm right?）：
对于a、b、c、d这四张牌，共有4!=24种排列。shuffle03!共有4次循环，每次循环中生成两个0..3的随机数（4中可能性）；转换一下说法就是，8个随机数，每个随机数随机取四个值中的一个，由此共有84=4096个排列，这也意味着总体来说是4096个等概率的排列，每一个这样的排列必然对应个牌的24种排列之一。4096无法整除24，即无法平均分配到24种牌的排列中。所以，无法满足目标2。
给出答案的牛人之后又补充了一下更通俗的证明： 假设现在手中四张牌在初始时候排列为a、b、c、d，现在之考虑c和d。shuffle03!()会执行4次循环，每次循环中随机选取两张牌（这两张牌可能是同一个，相当于有放回的抽样），调换这两张牌的位置。可知，一次循环里，有16个抽样结果(a,a)、(a,b)、(a,c)、(a,d)、(b,a)等，其中(a,b)代表a和b调换位置，这16个结果是等概率的。在这其中有(c,d)和(d,c)，即c和d调换位置的方式有两种。所以在一次循环中c和d调换位置的概率是1/8，不调换位置的可能性是7/8。由于有4次循环，这就是一个二项分布，故总体上来说：
- c和d调换位置这一事件调换位置的次数出现0次的概率是：(7/8)4 ≈ 58.6%
- c和d调换位置这一事件调换位置的次数出现1次的概率是：4 × (1/8) × (7/8)3 ≈ 33.5%
- c和d调换位置这一事件调换位置的次数出现2次的概率是：6 × (1/8)2 × (7/8)2 ≈ 7.18%
- c和d调换位置这一事件调换位置的次数出现3次的概率是：4 × (1/8)3 × (7/8) ≈ 0.68%
- c和d调换位置这一事件调换位置的次数出现4次的概率是：(1/8)4 ≈ 0.02%
所以最终牌c在牌d前面的概率是58.6% + 7.18% + 0.02% ≈ 65.8% ，牌c在牌d后面的概率是33.5% + 0.68% ≈ 34.2% 。很明显，shuffle03!()有问题。
如果循环的次数增加，则洗牌的效果会更好，即牌c在牌d前面的概率和牌c在牌d后面的概率越相近。
ruby自带的shuffle
# !/usr/bin/env ruby
# coding: UTF-8
arr = ['a', 'b', 'c', 'd']
p arr.shuffle
python也自带shuffle方法：
# !/usr/bin/env python
# coding: utf-8
import random
arr = ['a', 'b', 'c', 'd']
random.shuffle(arr)
print arr
其他方法
维基百科上关于洗牌算法的内容：Fisher–Yates shuffle。
Shuffling algorithm analysis给出了一个方法。在如何测试洗牌程序中也给出了更多的有趣但可能不对的方法，评论中也给出了一些方法。
洗牌算法与取样问题
这段内容是在2014-08-25号补充，我在《编程珠矶》第12章“取样问题”看到了洗牌算法的应用，记录一下。另外，蓄水池算法也可用于取样问题。
现有10个元素，需要从中随机的挑选2个作为样本，这就是一个取样问题。
我们先想一个简单的方法：
# !/usr/bin/env ruby
# coding: UTF-8
require 'set'
dataset = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
samples = Set.new()
while true
data = dataset[Random.rand(0..9)]
if not samples.include?(data)
samples.add(data)
end
if samples.length >= 2
break
end
end
p samples
也可以是使用洗牌算法来巧妙的解决该问题，我们将0到9这10个数字打乱，前两个数字即为样本的位置：
# !/usr/bin/env ruby
# coding: UTF-8
def shuffle01!(arr)
len = arr.length
arr2 = []
for i in 0..len-1
index = Random.rand(i..arr.length-1)
arr[i], arr[index] = arr[index], arr[i]
end
end
dataset = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
arr = (0..9).to_a
shuffle01!(arr)
puts dataset[arr[0]]
puts dataset[arr[1]]
实际上，此时对于shuffle01!()函数而言，其内的循环执行两次即可：
# !/usr/bin/env ruby
# coding: UTF-8
def shuffle01!(arr)
len = arr.length
arr2 = []
for i in 0..1 # 循环执行2次
index = Random.rand(i..arr.length-1)
arr[i], arr[index] = arr[index], arr[i]
end
end
dataset = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
arr = (0..9).to_a
shuffle01!(arr)
puts dataset[arr[0]]
puts dataset[arr[1]]