落叶知秋分享 http://blog.sciencenet.cn/u/wqfeng

博文

[转载]等概率随机排列数组(洗牌算法)

已有 2768 次阅读 2011-10-16 20:35 |个人分类:算法|系统分类:科研笔记|关键词:等概率洗牌| 等概率洗牌 |文章来源:转载

问题描述:假设有一个数组,包含n个元素。现在要重新排列这些元素,要求每个元素被放到任何一个位置的概率都相等(即1/n),并且直接在数组上重排(in place),不要生成新的数组。用 O(n) 时间、O(1) 辅助空间。

算法是非常简单了,当然在给出算法的同时,我们也要证明概率满足题目要求。

先想想如果可以开辟另外一块长度为n的辅助空间时该怎么处理,显然只要对n个元素做n次(不放回的)随机抽取就可以了。先从n个元素中任选一个,放入新空间的第一个位置,然后再从剩下的n-1个元素中任选一个,放入第二个位置,依此类推。

按照同样的方法,但这次不开辟新的存储空间。第一次被选中的元素就要放入这个数组的第一个位置,但这个位置原来已经有别的(也可能就是这个)元素了,这时候只要把原来的元素跟被选中的元素互换一下就可以了。很容易就避免了辅助空间。

用Python来写一段简单的程序描述这个算法:

1
2
3
4
5
6
7
from random import Random

def Shuffle(li):
  rand = Random()
  for x in xrange(len(li) - 1, 0, -1):  # 逆序遍历li
    y = rand.randint(0, x)              # 从剩余数据中随机选取一个
    li[x], li[y] = li[y], li[x]         # 将随机选取的元素与当前位置元素互换

主要的代码仅仅三行而已,浅显易懂。

来计算一下概率。如果某个元素被放入第i(1in)个位置,就必须是在前 i - 1 次选取中都没有选到它,并且第 i 次选取是恰好选中它。其概率为:

pi=n1n×n2n1××ni+1ni+2×1ni+1=1n

可见任何元素出现在任何位置的概率都是相等的。

实际上Python用户一定知道,在Random类中就有现成的shuffle方法,处理方法与我上面的程序是一样的。顺便也贴在这里学习一下。以下代码来自于 Python 2.5 Librandom.py:

250
251
252
253
254
255
256
257
258
259
260
261
262
def shuffle(self, x, random=None, int=int):
  """x, random=random.random -> shuffle list x in place; return None.

  Optional arg random is a 0-argument function returning a random
  float in [0.0, 1.0); by default, the standard random.random.
  """


  if random is None:
    random = self.random
  for i in reversed(xrange(1, len(x))):
    # pick an element in x[:i+1] with which to exchange x[i]
    j = int(random() * (i+1))
    x[i], x[j] = x[j], x[i]

转自:


http://blog.sciencenet.cn/blog-347232-497558.html

上一篇:[转载]MPQ技术内幕
下一篇:[转载]Google面试题中的两道趣题

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-9-19 02:10

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部