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

[lichgo]

比如产生一个1-10的乱序序列，数字不能重复出现。

讨论下有没有高效的算法。

[zhuzhuor]

#!/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]

T_T空格都被吃了...for后面两行有tab缩进，意会就行了...

[lldong]

《编程珠玑》里貌似第一章有道习题就是用楼上这种算法，

[Mutoo]

actionscript，一句话的事儿。

function randomArr(arr:Array):Array {
return arr.sort (function(){return Math.random ()>.5});
}

[phuslu]

@Mutoo python也比较简单
python -c "import random;print random.sample(xrange(10),10)"

[zhuzhuor]

@lidong 是说习题答案么，编程珠玑我一直想看却一直没看，不知道还有更好的算法没，感觉没输出一个数都要random一次，好的随机数生成器其实速度很慢呢

[annielong]

关键在于random函数，以前曾经有一篇文章专门研究这个的，看似简单实际很复杂。

[guoquan]

每个语言基本东哥个随机函数生成器和一个shuffle

[lisztli]

数字不能重复的话,还能叫随机码?

[lisztli]

理解错了
python random.shuffle

[lichgo]

嗯如果不用python、AS的函数呢？

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

或者说有没有人知道shuffle函数的底层算法是什么样的？

[reus]

http://svn.python.org/view/python/trunk/Lib/random.py?revision=73382&view=markup
都在这里了

[Mutoo]

简单说就是使用一个比较器（comparator），通常是一个函数，这个函数传入两个参数，例如a和b，返回一个整数，-1表示a应该放在b前面，0表示a和b等价，1表示a应该放在b后面

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

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

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

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

对给定1～10，这十个数字组成的有序数组，放到一个随机比较器中，就能得到不重复的乱序数组。

[zhuzhuor]

@lichgo 都不看我的代码啊...好歹我还第一个回复你呢，就用了一个随机数的函数，转换成c一样的

@lldong @reus 貌似python的shuffle就用的我的那个算法...就算不是最快，估计这个也是最简单明了的了吧?

[zhuzhuor]

@Mutoo 你不知道内部sort是怎么实现的啊，估计得跑nlogn个random函数呢

[lldong]

@zhuzhuor 对，第一章的习题答案里，不过是伪代码，不过在12章里有实现

[Mutoo]

@zhuzhuor 换序的方法是比较快。

[lichgo]

@zhuzhuor 当然有看的，你是第一个回复的人肯定看了。我的想法跟你的差不多，就没怎么评论。想看看其他人怎么想。Anyway，感谢关注。

[pursuit]

感觉也就是 洗牌算法 了吧

[antique]

谷歌到这里几年前的帖子，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;
}
}