📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Google/Microsoft : Random Shuffle

 
🔗
Imbalism 2011-4-26 09:46:30 | 只看该作者
全局:
回复  Imbalism

是的
GCC里面的STL的random_shuffle貌似就是这个算法
Etrnls 发表于 2011-4-26 09:26

谢谢,好像有点问题:
Algorithm P: Let x1,x2,....,xt be a set of t numbers to be shuffled
p1 [initialize] set j<- t.
p2 [Geerate U] generate a random number U, uniformly distribute between zero and on.
p3[exchange] set k = floor(jU) + 1(now k is a random integer, 1 to j), exchange xk, xj
p4[decrease j] j--, if j > 1, return p2;
上面抄自the art of computer programming vol2 secend edition.
j应该是递减的,而不是递增。希望你能再看看你的算法,不知道是不是这里有问题。

另外请问一下你关于gcc stl的实现是哪里看的呢?是在www.cplusplus.com 的reference里面查到一个学一个的,还是有其它系统的学习方法或者资料呢?
回复

使用道具 举报

🔗
lwy.tsinghua 2011-4-26 10:39:43 | 只看该作者
全局:
回复 11# Imbalism

j递减和递增是一样的,都可以用数学归纳法证明得到的序列是随机的。
现在证明j递增时算法的正确性:

1,假设当j=m时,0...m的各种排列都是等概率的
2,因为第m+1个元素出现在0...m+1的位置的可能性是等概率的
3,所以0...m+1个元素的各种排列也都是等概率的
因为很容易证明当j=2时,第0,1,2个元素的排列是等概率的,所以由归纳法可知,当j递增至n时,可以得到0...n的随机排列。

不知道这样解释对不对呢?
回复

使用道具 举报

🔗
Imbalism 2011-4-26 10:42:10 | 只看该作者
全局:
我有个朋友去腾讯面试,面试官问他如何把一副牌打乱顺序后发给玩家,和这个是一样的。

我当时的第一个想法是,人是怎么洗牌的就让电脑怎么洗牌。一开始总共有n张牌,产生两个随机数a=rand()%n,b=rand()%n,然后把a和b之间的牌移动到牌堆顶层。这时候牌堆顶部有b-a+1张牌,对这b-a+1张牌做前面一样的处理,也就是从中间抽出一部分再放到顶端,直到最后只剩1张牌。可以反复这样处理几遍。

后来自己也觉得上面那方法太麻烦了,老是要移动元素。就想简介点来个swap(rand()%n,rand()%n)。

刚才看到上面几位的回复,发现自己之前的想法真 ...
ljfljf2006 发表于 2011-4-26 08:41


玩过一次,一进游戏惊呼,这群英雄的技能都比我强好多,果然很IMBA
那天逛到论坛,一进论坛惊呼,这群同学的实力都比我强好多,真是很IMBA。
故起此名
回复

使用道具 举报

🔗
Imbalism 2011-4-26 11:57:07 | 只看该作者
全局:
回复  Imbalism

j递减和递增是一样的,都可以用数学归纳法证明得到的序列是随机的。
现在证明j递增时算法的正确性:

1,假设当j=m时,0...m的各种排列都是等概率的
2,因为第m+1个元素出现在0...m+1的位置的可能性是等概率的
3,所以0...m+1个元素的各种排列也都是等概率的
因为很容易证明当j=2时,第0,1,2个元素的排列是等概率的,所以由归纳法可知,当j递增至n时,可以得到0...n的随机排列。

不知道这样解释对不对呢?
lwy.tsinghua 发表于 2011-4-26 10:39


明白了,非常感谢你的耐心解答!
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-26 12:51:25 | 只看该作者
全局:
位置要分步均匀也就是说各个i(0 <= i < n)元素在各个j(0 <= j < n)位置上的概率相等.
for(int i=0;i<n;i++)  swap( x[n-1-i],x[rand()%(n-i)])的办法是等概率的:
对第一个选中的元素,它放到a[n-1]位置上,概率:1/n
对第二个选中的元素,它放到a[n-2]位置上,概率为 : 第一次没选中它的概率*第二次选中它的概率 == (n-1)/n*(1/n-1) = 1/n
对与第3个:..... ...... (n-1)/n*(n-2)/(n-1)*(1/(n-2)) == 1/n
......
概率均为1/n, 等概率,时间复杂度O(n),所以效率大于随机数排序
回复

使用道具 举报

🔗
Etrnls 2011-4-26 13:19:47 | 只看该作者
全局:
回复 11# Imbalism

STL源码剖析,侯捷。不过更多讲的是实现技巧而不是算法,虽然算法也有……
回复

使用道具 举报

🔗
Imbalism 2011-4-26 14:31:45 | 只看该作者
全局:
位置要分步均匀也就是说各个i(0
wwwyhx 发表于 2011-4-26 12:51

那如果这样的算法呢?
for (int i = 1; i < n; ++i) swap(x[i], x[rand() % (n)]);
任何一个元素分到每个位置上的概率也是相同的,那它是否是一个等概率的算法呢?
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-26 17:09:58 | 只看该作者
全局:
那如果这样的算法呢?
for (int i = 1; i < n; ++i) swap(x, x[rand() % (n)]);
任何一个元素分到每个位置上的概率也是相同的,那它是否是一个等概率的算法呢?
Imbalism 发表于 2011-4-26 14:31



    swap括号左边的那个x代表什么????
回复

使用道具 举报

🔗
Imbalism 2011-4-26 17:30:12 | 只看该作者
全局:
swap括号左边的那个x代表什么????
wwwyhx 发表于 2011-4-26 17:09


原数组,我直接改楼上的。这个举个反例,就是说有的情况下,虽然每个元素在各个位置上概率相等(1/n),但是还是不能说它是进行均匀分布的。要证明每种排列出现的概率相等(1/n!),才能说它们是均匀分布的。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-26 17:52:12 | 只看该作者
全局:
原数组,我直接改楼上的。这个举个反例,就是说有的情况下,虽然每个元素在各个位置上概率相等(1/n),但是还是不能说它是进行均匀分布的。要证明每种排列出现的概率相等(1/n!),才能说它们是均匀分布的。
Imbalism 发表于 2011-4-26 17:30



    当然可以证明,这两个命题就是等价的。

    如果按那种swap的方法,各个元素在位置各个位置上的概率为1/n

那么对于任意一种组合:a1a2....an,这个组合出现的概率为(a1出现在第一个位置的概率)×(在a1出现在第一个位置的情况下a2出现在第二个位置的概率)×(在a1出现在第一个位置,a2出现在第二个位置的情况下a3出现在第3个位置的概率)×.....

a1出现在第一个位置上的概率是1/n
在a1出现在第一个位置的情况下a2出现在第二个位置的概率为1/(n-1)
a3在前两条情况成立的情况下出现在第三个位置的概率是1/(n-2)
....
.....
这样,整个排列出现的概率就是(1/n)*(1/(n-1))*(1/(n-2))...*1/1 = 1/n!

点评

赞  发表于 2012-10-2 09:07
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表