小花鹿请进。关于随机不重复抽取 算法之 【数组经典洗牌法】原理

香川群子

洗牌法倒序输出的代码：

1. Sub GetRndRev(arr, a, b, n)
   
2.     Randomize
   
3.     m = UBound(arr)
   
4.     For i = m To m - n + 1 Step -1 '倒序洗牌
   
5.         r = Int(Rnd() * (b - a + 1 - (m - i))) + a + (m - i)
   
6.         t = arr(r): arr(r) = arr(b - (m - i)): arr(i) = t '一维代码倒序
   
7.     Next
   
8.    
   
9. '    For i = m To 1 Step -1  '倒序洗牌 m to 1 简化代码
   
10. '        r = Int(Rnd() * i) + m - i + 1
    
11. '        t = arr(r): arr(r) = arr(i): arr(i) = t  '一维代码倒序
    
12. '    Next
    
13.    
    
14. End Sub

复制代码

香川群子

能够处理二维数组的随机乱序的 【经典数组洗牌法】代码：

Sub GetRndArr(arr, a, b, n, Optional k = 0)
    Randomize
    If k < 0 Then l = LBound(arr, 2) Else l = LBound(arr)
    For i = l To n + l - 1 '多行多列数组正序洗牌
        r = Int(Rnd() * (b - a + 1 - (i - l))) + a + (i - l)
        If k = 0 Then
            t = arr(r): arr(r) = arr(i + a - l): arr(i) = t '下标1开始一维代码
        ElseIf k = 1 Then
            For j = LBound(arr, 2) To UBound(arr, 2)
                t = arr(r, j): arr(r, j) = arr(i + a - l, j): arr(i, j) = t '行洗牌多列数组移动
            Next
        ElseIf k = -1 Then
            For j = LBound(arr) To UBound(arr)
                t = arr(j, r): arr(j, r) = arr(j, i + a - l): arr(j, i) = t '列洗牌多行数组移动
            Next
        End If
    Next
End Sub

香川群子

gjj136138139 发表于 2012-6-20 21:05
不重复的数列
三步方案：

这个当然可以……如果你原始数据已经整齐地排列在工作表的单列里……
但是如果你需要随机乱序的对象只是VBA内存数组结果，且只是中间计算过程等等……
那么如果可以直接在VBA代码的内部过程中解决的话……

你就没有必要：
1. 把数组结果输出到工作表
2. 用上述方法乱序
3. 再把数据读回VBA内存数组。
4. 清理、打扫战场，抹去刚才的痕迹。

小花鹿

香川群子 发表于 2012-6-20 21:01
接3楼。

【经典数组洗牌法】的真正原理是：

先理解了这个例子再说。
根据你的讲解，我写了一段代码：
Sub test()
Dim i&, ar(1 To 10), br(1 To 3), r&, tm&
For i = 1 To 10
    ar(i) = i
Next i
For i = 1 To 3
    r = Int(Rnd * (10 - i + 1)) + i
    tm = ar(i)
    ar(i) = ar(r)
    ar(r) = tm
    br(i) = ar(i)
Next i
[a1:c1] = br
End Sub
目的是从按大小排列的1到10的数组ar中随机抽取不重复的3个元素，按你的讲解我也解释一下，请指导：
i 是从1 到3循环的，
当 i=1 时，10-i+1=10 ，由于0<=rnd<1，所以 Int(Rnd * (10 - i + 1)) 得到的结果是0到9，加上 i 后是1到10，即 r=1到10，从第1到第10个元素中抽取，假设 r=6，即抽取了第6个元素，通过下面的一系列赋值 ar 数组的结果是 6,2,3,4,5,1,7,8,9,10
当 i=2 时，10-i+1=9，由于0<=rnd<1，所以 Int(Rnd * (10 - i + 1)) 得到的结果是0到8，加上 i 后是2到10，即 r=2到10，即从第2到第10个元素中抽取，由于 r 不可能等于1，所以第1个元素6是根本抽不到的，这就避免了重复抽取，假设这时 r=5,即抽取第5个元素，通过下面一系列的赋值 ar 数组就变成了这样的，6,5,3,4,2,1,7,8,9,10
当 i=3 时，10-i+1=8， Int(Rnd * (10 - i + 1)) 得到的结果是0到7，加上 i 后是3到10，即 r=3到10，从第3到第10个元素中抽取，由于同样的原因，处于第1，2位的6和5是抽不到的，假设这时 r=9，经过赋值后 ar 变成了这样的，6,5,9,4,2,1,7,8,3,10
在这里，最重要的是两方面，一是要确定 r 的取值范围，这由Int(Rnd * (10 - i + 1)) + i 决定，这个范围一定要把已经取出的元素排除在外，二是当确定了取哪个元素后，要重新对已取出的和未取过的元素进行摆放，从而将两者分开，以便于后面方便确定取值范围。
注：我这里的 br 数组是多余的。

小花鹿

香川群子 发表于 2012-6-20 21:01
接3楼。

【经典数组洗牌法】的真正原理是：

Randomize的解释还是不明白，看了帮助也不明白。

liucqa

支持一下        

jiminyanyan

支持一下   

香川群子

小花鹿 发表于 2012-6-21 00:23
Randomize的解释还是不明白，看了帮助也不明白。

灰袍法师对rand随机函数有较深的分析。


我也只能根据自己的理解，说一下，但可能不一定正确。

=rand()工作表函数，以及=rnd() VBA函数，
其原理大致是内置了一种算法，可以生成一组=2^24=16777216 即将近1千7百万个乱序数列。

由于这个乱序数列是由同一个算法得来的，因此实际上它不是真正意义上的随机系列，
而是一个重复频率=16777216的固定乱序数列。

…………
至于我们使用这个函数时，
系统会默认以当前时刻timer为省略参数，去搜寻16777216中对应的那一个数，
比如=2202268，并返回其结果=2202268/16777216=0.131265402


然后，接下来，就完全按照这一个乱数序列中的初始位置开始，
根据用户的需要，一直向下返回下一个乱数，
虽然是1千7百个数中的一个乱数，看上去毫不重复，
但其实却是按照一定算法获取的乱数序列中的有规律的乱数了。


…………

并且，每次工作表保存以后，再次打开时，如果没有指定，
则下一次返回的乱数，都是这个庞大的1千7百万个乱数序列中的下一个位置的同一个乱数。


举个例子，
你如果在一个工作表中写入了=rand()函数，或使用VBA中的=rnd()返回了一个或一系列的随机值，
然后你保存这个工作表，关闭文件。

这以后，你每次打开这个文件以后，再次操作，记住新的乱数（随机值）

然后不要保存文件而直接关闭文件，

接着再打开文件，再次操作，
你将发现，每次打开同一个未更新保存过的文件时，
系统返回的随机乱数，实际上将会是一个一模一样的即初始状态一样的不变的数值了。
（即，系统返回由同一个位置开始的乱数系列。）


…………

为了防止出现这种随机数不给力的现象，
设置了Randomize 语句命令，
则VBA执行这个语句时，会以当前系统时刻为参数(种子seed)，到1千7百万个乱数序列中去重新寻找一个不同的开始位置。


这个就是Randomize 语句的作用。

简单说是为了防止每次代码执行随机函数时，返回相同系列的乱数。

小花鹿

讲得很好，谢谢，那么这样说来把它放在循环中岂不更好？

香川群子

小花鹿 发表于 2012-6-21 10:20
讲得很好，谢谢，那么这样说来把它放在循环中岂不更好？

没这个必要。


因为，Randomize 的作用是：
每次执行代码之前，
把这1千7百万乱序数列的起始位置进行初始化就OK啦。


这以后，即使是按照顺序返回这个乱序数列的值，也足够【乱】了。

没有必要每次从乱序中找一个乱序位置开始。
这样做实际返回乱序的程度是一样的概率。