V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lichgo
V2EX  ›  数学

讨论下乱序数字序列随机产生的算法

  •  
  •   lichgo · 2012-03-18 10:56:24 +08:00 · 9252 次点击
    这是一个创建于 4618 天前的主题,其中的信息可能已经有所发展或是发生改变。
    比如产生一个1-10的乱序序列,数字不能重复出现。

    讨论下有没有高效的算法。
    20 条回复    2015-03-01 21:24:44 +08:00
    zhuzhuor
        1
    zhuzhuor  
       2012-03-18 11:05:33 +08:00
    #!/usr/bin/env python

    from random import randint

    n = range(1, 11)

    for i in range(10):
    idx = randint(i, 9)
    n[i], n[idx] = n[idx], n[i] #交换位置

    print n

    估计这样算比较好吧


    不过python有shuffle函数
    zhuzhuor
        2
    zhuzhuor  
       2012-03-18 11:06:29 +08:00
    T_T空格都被吃了...for后面两行有tab缩进,意会就行了...
    lldong
        3
    lldong  
       2012-03-18 11:24:37 +08:00
    《编程珠玑》里貌似第一章有道习题就是用楼上这种算法,
    Mutoo
        4
    Mutoo  
       2012-03-18 12:01:36 +08:00
    actionscript,一句话的事儿。

    function randomArr(arr:Array):Array {
    return arr.sort (function(){return Math.random ()>.5});
    }
    phuslu
        5
    phuslu  
       2012-03-18 12:04:51 +08:00
    @Mutoo python也比较简单
    python -c "import random;print random.sample(xrange(10),10)"
    zhuzhuor
        6
    zhuzhuor  
       2012-03-18 12:11:16 +08:00
    @lidong 是说习题答案么,编程珠玑我一直想看却一直没看,不知道还有更好的算法没,感觉没输出一个数都要random一次,好的随机数生成器其实速度很慢呢
    annielong
        7
    annielong  
       2012-03-18 12:38:37 +08:00
    关键在于random函数,以前曾经有一篇文章专门研究这个的,看似简单实际很复杂。
    guoquan
        8
    guoquan  
       2012-03-18 13:03:12 +08:00
    每个语言基本东哥个随机函数生成器和一个shuffle
    lisztli
        9
    lisztli  
       2012-03-18 13:09:07 +08:00
    数字不能重复的话,还能叫随机码?
    lisztli
        10
    lisztli  
       2012-03-18 13:10:19 +08:00
    理解错了
    python random.shuffle
    lichgo
        11
    lichgo  
    OP
       2012-03-18 13:34:10 +08:00
    嗯如果不用python、AS的函数呢?

    毕竟是讨论算法而不是找API之类的函数。

    或者说有没有人知道shuffle函数的底层算法是什么样的?
    reus
        12
    reus  
       2012-03-18 13:45:47 +08:00
    Mutoo
        13
    Mutoo  
       2012-03-18 13:56:23 +08:00
    简单说就是使用一个比较器(comparator),通常是一个函数,这个函数传入两个参数,例如a和b,返回一个整数,-1表示a应该放在b前面,0表示a和b等价,1表示a应该放在b后面

    然后遍历一个数组,每次取两个数放到比较器中,根据返回的整数重新排放两个数

    如果比较器规定大数在前,小数在后,那么整个过程下来就能一个由大到小的数组。

    如果比较器规定小数在前,大数在后,那么可以得到由小到大的数组。

    如果比较器规定每次比较都随机摆放,那么就能得到乱序数组。

    对给定1~10,这十个数字组成的有序数组,放到一个随机比较器中,就能得到不重复的乱序数组。
    zhuzhuor
        14
    zhuzhuor  
       2012-03-18 14:06:01 +08:00
    @lichgo 都不看我的代码啊...好歹我还第一个回复你呢,就用了一个随机数的函数,转换成c一样的

    @lldong @reus 貌似python的shuffle就用的我的那个算法...就算不是最快,估计这个也是最简单明了的了吧?
    zhuzhuor
        15
    zhuzhuor  
       2012-03-18 14:07:54 +08:00
    @Mutoo 你不知道内部sort是怎么实现的啊,估计得跑nlogn个random函数呢
    lldong
        16
    lldong  
       2012-03-18 14:12:00 +08:00
    @zhuzhuor 对,第一章的习题答案里,不过是伪代码,不过在12章里有实现
    Mutoo
        17
    Mutoo  
       2012-03-18 14:12:15 +08:00
    @zhuzhuor 换序的方法是比较快。
    lichgo
        18
    lichgo  
    OP
       2012-03-18 14:24:03 +08:00
    @zhuzhuor 当然有看的,你是第一个回复的人肯定看了。我的想法跟你的差不多,就没怎么评论。想看看其他人怎么想。Anyway,感谢关注。
    pursuit
        19
    pursuit  
       2012-03-19 18:47:18 +08:00
    感觉也就是 洗牌算法 了吧
    antique
        20
    antique  
       2015-03-01 21:24:44 +08:00
    谷歌到这里几年前的帖子,1楼说的简单换序存在概率问题,参见分析
    http://coolshell.cn/articles/8593.html
    手头碰到的问题用这两种方法测试,结果确实不同,影响不小。

    正确的随机是 Fisher_Yates洗牌算法(测试正确)
    void ShuffleArray_Fisher_Yates(char* arr, int len)
    {
    int i = len, j;
    char temp;

    if ( i == 0 ) return;
    while ( --i ) {
    j = rand() % (i+1);
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    }
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2812 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 02:04 · PVG 10:04 · LAX 18:04 · JFK 21:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.