这种洗牌算法还不是完全随机？

haitao

[ 本帖最后由 haitao 于 2012-10-24 16:55 编辑 ]

这种洗牌算法还不是完全随机？
算法a：顺序在数组s(下标1-n)的n个元素里填入1-n
循环i=1到n
  x=rand(n+1)
  if x<>i then 交换s[i]和s[x]
据说完全随机的应该是
算法b：循环i=n到2
  x=rand(i)
  if x<>i then 交换s[i]和s[x]

据说原因是：算法a第1次移动后，第1个数还在第1个位置的概率是1/n，后续移动只会减少这个概率
感觉不对啊，后续移动也可能把移到别的位置的1换回第1个位置。。。。

伪随机算法的效果验证，好像一直是很困难的事情
本例是利用伪随机算法的一个应用算法了，应该简单很多

算法a，可能：1234567.。。
i=1时，x=3，则3214567.。。。
i=2时，x=5，则3514267....
i=3时，x也可能=1，则153267.。。

按理说，算法a的每次交换，都是一个独立的随机过程，它没有存在任何偏好

算法a：循环i=1到n
  x=rand(n+1)
  if x<>i then 交换s[i]和s[x]

和

算法c：循环i=1到n
  y=rand(n+1)
  x=rand(n+1)
  if x<>y then 交换s[y]和s[x]

应该是一样的效果吧

如果按那个否定的原因，算法c的交换就没有a那个1/n的问题了？肯定随机了！？


但是，实际的运行结果有点出乎意料：
刚才写了个程序把3个算法都演示了100万次（n=10）
累计：每次结果里，1在每个位置出现的次数
最后以它的方差（是这个词吧）总和为标准——这个标准不知道有没有问题
发现算法c的方差反而最大！a和b其实差不多。。。。

99871 99765 100530 99988 100019 100038 99705 100539 99760 99785
836086
99921 99589 100306 100009 100270 99663 100485 99281 99861 100615
1605080
195903 89164 89722 89423 89009 89317 89614 88985 89557 89306
1629925602

99976 99833 99663 100404 100176 100126 99969 100254 99943 99656
539164
99644 100416 99867 100286 99809 100674 99717 100253 99449 99885
1350958
197071 89278 89280 89561 89487 89130 89306 89146 89034 88707
1880332880

100510 99108 99826 99596 100159 100052 100244 100100 99911 100494
1598734
100303 100493 100005 100063 99910 100276 99749 99729 99553 99919
765940
197136 89039 88993 89574 88943 89141 89309 89374 89793 88698
1894769490

100312 99760 99802 99699 100307 99883 100181 99792 100315 99949
570538
99820 100070 100102 100368 99558 100028 99923 100332 99753 100046
558554
197516 89013 89277 89320 88728 88957 89776 89433 88750 89230
1976947860


如果每个算法每次都洗5遍，则大家都差不多了：

100171 100195 100592 99613 100052 99918 100367 99759 100001 99332
1215922
100516 100077 99679 100325 99588 99954 99927 100443 100117 99374
1259854
99775 100310 100275 100326 99658 100043 99580 99792 99727 100514
1005828

100137 100162 100426 99756 100151 99960 100149 99972 99795 99492
633500
100254 100129 99870 99879 99905 100027 100386 99907 99713 99930
367366
100298 100029 100050 100043 100269 99907 99973 99712 100333 99386
746562

100612 100144 99809 100349 100117 99799 99591 99274 100173 100132
1349362
100183 99665 99926 99737 100476 99638 100015 99697 100131 100532
970198
99674 100183 99882 99742 99951 100577 99694 100215 100103 99979
706494

100490 99980 100350 100053 99431 100229 99984 99633 99701 100149
988558
99914 99540 99684 100163 99977 99985 100279 100184 99973 100301
549202
100281 99775 100043 100243 100207 99991 99610 99788 99778 100284
560398

cjaizss

hbmhalley 发表于 2012-10-26 12:16
回复 14# cjaizss

对，没错，b的确是平均分布。产生不同的随机序列直接导致最后序列不一样。

hbmhalley

回复 14# cjaizss


    奇排序 .. 是个毛?
    逆序为奇的排列?
.....

cjaizss

hbmhalley 发表于 2012-10-26 11:51
回复 11# cjaizss

其实很简单，b算法中只会产生奇排序或者偶排序，首先砍掉一半
以上我的认为错了，想想

hbmhalley

回复 11# cjaizss


    求详解

    我的想法：假如 rand_i() 表示 rand()%i , 且每个 rand_i 在各自值域 [0,i) 内返回每种可能的概率是相同的，那么连续调用 rand_n .. rand_1 所对应的共 n! 种排列被产生的概率也是相同的，而这里的任两种排列被 b 算法用到后都会导致 b 算法输出不同的结果，且总结果数也是 n! ，那么连续调用 rand_n .. rand_1 所产生的等概率的序列与每种结果相对应。

liuiang

此贴顺序为什么是降序排列的。

cjaizss

hbmhalley 发表于 2012-10-26 11:44
回复 9# cjaizss

是的，b也不满足

hbmhalley

回复 9# cjaizss


    b 也不满足吗?

cjaizss

haitao 发表于 2012-10-26 11:00
假设伪随机函数已经足够随机了
这样的洗牌还不满足平均分布？

不满足平均分布，但已经相对接近平均分布了

haitao

cjaizss 发表于 2012-10-26 10:46
作为洗牌其实这样不错了，挺好用的。
但做为数学意义来说，我可以负责的说算法结束后的排列不满足平均分 ...

假设伪随机函数已经足够随机了
这样的洗牌还不满足平均分布？

另外，a和b真的有差别吗？