洗牌算法


#算法#


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]]

( 本文完 )