如何生成均匀随机排列(等概率生成排列)

      这个算法的应用,比如洗牌,这个大家都非常熟悉。很久以前用的是最原始的方法,就是一直rand()未出现的牌,直至生成所有的牌。
这当然是一个while(1)循环,很烂的算法吧。后面听说直接交换牌,打乱即可了。但是打乱后生成的排列是随机的么,是等可能随机的么。
其实,这个问题上算法导论上早已经有了答案了,看过算法导论之后觉得没看之前真的是算法修养太差了。
      算法的伪代码如下图所示:
      
      
      具体c++实现如下:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
// void Swap(int& nOne, int& nTwo)
// {
// nOne = nOne + nTwo;
// nTwo = nOne - nTwo;
// nOne = nOne - nTwo;
// }
void Swap(int& nOne, int& nTwo)
{
    int nTemp;
    nTemp = nOne;
    nOne = nTwo;
    nTwo = nTemp;
}
//返回一个在区间[nBeg, nEnd]内的随机数
int Random(int nBeg, int nEnd)
{
    assert(nEnd >= nBeg);
    if (nBeg == nEnd)
    {
        return nBeg;
    }
    else
    {
        return rand() % (nEnd - nBeg + 1) + nBeg;
    }
}
void RandomizeInPlace(int* pnA, int nLen)
{
    static bool s_bFirst = false;
    if (!s_bFirst)
    {
        srand(time(NULL));
        s_bFirst = true;
    }
    
    for (int i = 0; i < nLen; ++i)
    {
        Swap(pnA[i], pnA[Random(i, nLen - 1)]);
    }
}
int main()
{
    int nArray[20];
    int i, j;
    for (i = 1; i <= 20; ++i)
    {
        int nCnt = i;
        while (nCnt--)
        {
            for (j = 0; j < i; ++j)
            {
                nArray[j] = j;
            }
            RandomizeInPlace(nArray, i);
            for (j = 0; j < i; ++j)
            {
                printf("%d ", nArray[j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

   运行效果图片如下:

   根据运行结果大致就可以感觉到,生成的排列都是随机的。
   这里要多说一句那就是我注释的那个交换函数其实是有bug的,也许这才是不提倡使用这个交换方法的真正原因,而不仅仅是
难以理解。用同一个变量去调用该函数,会将该变量置0,而不是保持原来的值!!!

   至于如何证明这个算法生成的均匀随机的排列,可以参考算法导论5.3节最后一部分。
   证明的大致思路是利用循环不变式的证明方法:证明i次循环后得到某个排列的概论是(n -i)! / n!,那么n次循环后得到最终那个排列的
概论就是1/n!,这样就证明了该算法能够得到均匀随机排列。
   这个算法其实就是随机化算法的一种,其实快排也有所谓的随机化版本,改动的地方只是随机选择了中轴元素而已,这个
在算法导论上也有介绍。

posted on 2012-02-26 16:07 yx 阅读(3213) 评论(8)  编辑 收藏 引用 所属分类: 随机算法

评论

# re: 如何生成均匀随机排列(等概率生成排列) 2012-02-26 20:39 driftfly

rand本身不是随机  回复  更多评论   

# re: 如何生成均匀随机排列(等概率生成排列) 2012-02-26 21:45 远行

这个算法本身就是建立在它是随机基础上的,伪代码里面那个Randomize,当然实现的时候也假设了rand()是随机的了,至于它的随机程度就不考虑了,你也可以采用更好的生成随机数的接口@driftfly
  回复  更多评论   

# re: 如何生成均匀随机排列(等概率生成排列) 2012-02-27 20:28 cmdblock

其实就是双随机而已,既随机牌的大小又随机位置。不过这种方法,个人觉得一般般啦  回复  更多评论   

# re: 如何生成均匀随机排列(等概率生成排列) 2012-02-27 21:29 远行

这个算法主要是可以证明等概率打乱排列@cmdblock
  回复  更多评论   

# re: 如何生成均匀随机排列(等概率生成排列) 2012-08-10 10:12 peakflys

挺好的方法,无论是从空间上还是时间上 都是不错的算法  回复  更多评论   

# re: 如何生成均匀随机排列(等概率生成排列) 2012-10-16 12:25 liyonghelpme

有一种多项式生成排列的方式可以看看~~
http://en.wikipedia.org/wiki/Permutation_polynomial  回复  更多评论   

# re: 如何生成均匀随机排列(等概率生成排列) 2013-10-09 10:15 justcyf

for (j = 0; j < i; ++j)

{

nArray[j] = j;

}

main函数里面的这段,第一行是不是写错了?应该为for(j = 0;j<20;++j)  回复  更多评论   

# re: 如何生成均匀随机排列(等概率生成排列) 2013-10-09 10:17 justcyf

sorry,看错了。。。@justcyf
  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜