这是一个创建于 4668 天前的主题，其中的信息可能已经有所发展或是发生改变。
比如产生一个1-10的乱序序列，数字不能重复出现。
讨论下有没有高效的算法。
讨论下有没有高效的算法。
 |
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函数 |
|
2
zhuzhuor 2012-03-18 11:06:29 +08:00
T_T空格都被吃了...for后面两行有tab缩进，意会就行了...
|
 |
3
lldong 2012-03-18 11:24:37 +08:00
《编程珠玑》里貌似第一章有道习题就是用楼上这种算法，
|
 |
4
Mutoo 2012-03-18 12:01:36 +08:00
actionscript，一句话的事儿。
function randomArr(arr:Array):Array { return arr.sort (function(){return Math.random ()>.5}); } |
 |
5
phuslu 2012-03-18 12:04:51 +08:00
@Mutoo python也比较简单
python -c "import random;print random.sample(xrange(10),10)" |
|
6
zhuzhuor 2012-03-18 12:11:16 +08:00
@lidong 是说习题答案么，编程珠玑我一直想看却一直没看，不知道还有更好的算法没，感觉没输出一个数都要random一次，好的随机数生成器其实速度很慢呢
|
 |
7
annielong 2012-03-18 12:38:37 +08:00
关键在于random函数，以前曾经有一篇文章专门研究这个的，看似简单实际很复杂。
|
 |
8
guoquan 2012-03-18 13:03:12 +08:00
每个语言基本东哥个随机函数生成器和一个shuffle
|
 |
9
lisztli 2012-03-18 13:09:07 +08:00
数字不能重复的话,还能叫随机码?
|
|
10
lisztli 2012-03-18 13:10:19 +08:00
理解错了
python random.shuffle |
 |
11
lichgo OP 嗯如果不用python、AS的函数呢？
毕竟是讨论算法而不是找API之类的函数。 或者说有没有人知道shuffle函数的底层算法是什么样的？ |
 |
12
reus 2012-03-18 13:45:47 +08:00
|
|
13
Mutoo 2012-03-18 13:56:23 +08:00
简单说就是使用一个比较器（comparator），通常是一个函数，这个函数传入两个参数，例如a和b，返回一个整数，-1表示a应该放在b前面，0表示a和b等价，1表示a应该放在b后面
然后遍历一个数组，每次取两个数放到比较器中，根据返回的整数重新排放两个数 如果比较器规定大数在前，小数在后，那么整个过程下来就能一个由大到小的数组。 如果比较器规定小数在前，大数在后，那么可以得到由小到大的数组。 如果比较器规定每次比较都随机摆放，那么就能得到乱序数组。 对给定1～10，这十个数字组成的有序数组，放到一个随机比较器中，就能得到不重复的乱序数组。 |
|
14
zhuzhuor 2012-03-18 14:06:01 +08:00
|
|
18
lichgo OP @zhuzhuor 当然有看的，你是第一个回复的人肯定看了。我的想法跟你的差不多，就没怎么评论。想看看其他人怎么想。Anyway，感谢关注。
|
 |
19
pursuit 2012-03-19 18:47:18 +08:00
感觉也就是 洗牌算法 了吧
|
 |
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; } } |
Select Language