生成不重复随机整数的各种算法－加生成结果的简单检验

灰袍法师 · 发表于 2011-2-5 20:34

原帖的大量讨论在这里，由于楼层太多几乎没人看下去，而且楼主已经弃楼，所以再开一帖方便继续讨论

生成不重复随机数的一段代码
http://club.excelhome.net/redire ... 300&ptid=676313

总结题目：
从一个指定的范围m，生成指定数量n个不重复随机整数,等于从范围内的m个整数，随机抽样n个，然后随机排序

许多算法都用了洗牌算法，其优缺点如下：
优点是：速度很快，实现也很简单。

缺点是：洗牌算法似乎只能打乱一个已经存在的序列，而不能保证随机从范围内抽样。
我发现洗牌一次肯定不能达到随机抽样，抽样的均值和标准差都离数学期望值相当远

目前最快的三个算法如下：
lsftest提出的分段生成＋洗牌，也有上述缺点，我发现除非至少洗牌两次，否则抽样很不均匀，结果导致整个VBA的速度也没有理论上的快了

Zamyi提出的根据当前随机整数，按平均步长，等概率生成下一个随机整数
在抽样很少(<50)的时候会出错，而且抽样结果严重偏差
但是在抽样很多的时候却没啥问题，速度一样很快，而且可能是限制了步长取值的原因，生成的结果甚至比其余算法更加平均

最后，我提出的把整个抽样范围看作大蛋糕，随机分给每个抽样，这个算法似乎也可以均匀抽取，然后洗牌一次打乱顺序就可以了。

其实这三个算法的速度差异可以忽略，算法都是O(n)乘以常数，绝对可以保证每分钟抽样千万以上，够用了。

不过简单验证随机性和均匀性的VBA程序，还需要继续深入设计，说不定还能挖掘出某些算法特别之处，也进一步确保结果的均匀性和随机性。

[ 本帖最后由灰袍法师于 2011-2-5 21:59 编辑 ]

Admin · 发表于 2011-2-7 12:30

很遗憾通知楼上朋友，您的帖子在24小时之内没有任何回复！

通常情况下，本论坛发布的主题帖会在8小时被回复或处理。您的帖子在24小时之内未被回复，其中的原因可能是：

1、问题表述不清、模棱两可，难以理解，帮助者被搞晕了，夺帖而出；
2、没有上传必要的附件，或附件被遗忘在某个角落；
3、发帖提问时，语气带棱角、带挑衅，不幸被列入不受欢迎的帖子；
4、所提问题不成立，或提不合理的要求，乐于助人者使出“走为上”之计；
5、话题较偏、较冷或者发布到了不合适的版块，暂时无人问津，顾影自怜。

为了提高您的问题解决效率，我们推荐您阅读以下文章：
* 如何发表新话题和上传附件：http://club.excelhome.net/thread-45649-1-1.html
* 发帖的技巧：http://club.excelhome.net/thread-176339-1-1.html
* EH技术论坛的最佳学习方法：http://club.excelhome.net/thread-117862-1-1.html

白云2011 · 发表于 2011-4-17 23:26

不错，谢谢了。

lhmlhmlhm21 · 发表于 2012-2-23 21:11

支持法师了。法师是高人。

410223589 · 发表于 2012-8-2 12:23

非常感谢法师，对我很有帮助，谢谢了

gjj136138139 · 发表于 2012-8-2 12:31

支持。顶起来。

aoe1981 · 发表于 2014-5-5 09:07

法师，利用字典实现随机数的去重不是很方便吗？过一会再研究一下……

香川群子 · 发表于 2014-8-28 22:11

aoe1981 发表于 2014-5-5 09:07
法师，利用字典实现随机数的去重不是很方便吗？过一会再研究一下……

我很早以前就研究过此问题。

只是没有公开发布而已。

今天正好看到此贴，就正式发布一下。

Sub kagawa() '指定区间内均匀随机取不重复值按指定列数输出
' Dim a, b, c(), d, f(), h, i, l, m, n, r, t '因为数值个数会超Long范围，所以不应该定义数据类型
d = [d2] '小数位数d 用法同=Round(,numdecimalplaces)的第2参数零为整数、正数为小数、负数为个十百千位向上取整
a = [a2] * 10 ^ d '取值下限、自动按小数位设置扩大/缩小
b = [b2] * 10 ^ d '取值上限、自动按小数位设置扩大/缩小
m = [c2] '取值个数 F2单元格中公式计算取值允许个数 =IF(E2,INT((B2-A2)*10^D2/E2)+1,"无限")
h = [e2] '最小间隔步长 h=0时允许重复。而h不为零时如取值个数大于取数范围则取数不足部分返回=0
l = [g2] '输出时列数指定行数自动=m\l
r = [h2] '输出时是否排序 r=0时返回随机乱序(数组洗牌法)、r=1时按从小到大升序输出
Randomize
ReDim c(m - 1) '按取值个数定义存放结果的数组c
If b - a < m * h Then c(0) = a Else c(0) = Int(((b - a + 1) / m - h) * Rnd) + a '首位取值*Rnd即可
' n = 0 当前取值个数
Do
If b - c(n) < (m - n) * h Then
If c(n) + h > b Then Exit Do Else c(n + 1) = c(n) + h
Else
c(n + 1) = c(n) + Int(((b - c(n) + 1) / (m - n) - h) * Rnd * 2) + h
'取数原理为：上个值c(n) + 剩余范围(b - c(n) + 1) 除以剩余个数(m - n)得到的均匀区间
' 并扣除最小间隔h然后乘以2倍随机数 Rnd*2 取值再加上最小间隔h
'其中关键是要乘以2倍随机数 Rnd*2 取值这是因为Rnd的期望平均值=0.5
End If
n = n + 1
Loop Until n = m - 2 '到剩下最后一个时停止 (因最后一个的计算方法不同)
If c(n) + h <= b Then c(m - 1) = c(n) + Int((b - c(n) + 1 - h) * Rnd) + h '末位取值*Rnd即可
ReDim f(m \ l, l - 1) '按指定列数计算所需行数后定义存放结果的数组f
If r = 0 Then 'r=0时返回随机乱序(数组洗牌法)
For i = 0 To m - 1
r = Int((m - i) * Rnd) + i '数组洗牌算法进行不重复随机乱序抽取
t = c(r): c(r) = c(i): c(i) = c(r) '抽取后进行位置交换保证不重复以及无遗漏
f(i \ l, i Mod l) = t / 10 ^ d '结果按指定小数位换算
Next
Else 'r=1时按从小到大升序输出
For i = 0 To m - 1
f(i \ l, i Mod l) = c(i) / 10 ^ d '结果按指定小数位换算
Next
End If
[a5].CurrentRegion.Offset(1) = ""
[a6].Resize(m \ l + 1, l) = f '按指定列数输出结果
End Sub

复制代码

香川巨量随机取数20140828.rar (22.55 KB, 下载次数: 84)

7176386 · 发表于 2015-3-28 20:59

收藏以后学习！感谢分享

		自动登录	找回密码
密码			免费注册

[讨论] 生成不重复随机整数的各种算法－加生成结果的简单检验

〖Excel Home友情提示〗

评分

[讨论] 生成不重复随机整数的各种算法 － 加生成结果的简单检验

〖Excel Home友情提示〗

评分

[讨论] 生成不重复随机整数的各种算法－加生成结果的简单检验