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

vbaplus

香川群子 发表于 2013-1-22 22:44
理论上，如果每次a都比起始位置大，那么交换只要两次就可以了，不用回填到 i + a - l 位置了。

不过， ...

恩，我运用一下洗牌法哈~
要求生成n位随机数，这其中必须包含不重复的1,2,3,4四个数：

1. Function getRnd(n&)
   
2. If n < 4 Then Exit Function
   
3. Dim arrGD(), arrRd, r&, t
   
4. arrRd = Array(0, 5, 6, 7, 8, 9)
   
5. ReDim arrGD(1 To n)
   
6. Randomize
   
7. For i = 1 To n
   
8.   If i <= 4 Then arrGD(i) = i Else arrGD(i) = arrRd(Int(Rnd * 6))
   
9. Next i
   
10. For i = 1 To n
    
11.    r = Int(Rnd * (n - i + 1)) + i
    
12.    t = arrGD(r): arrGD(r) = arrGD(i): arrGD(i) = t
    
13. Next i
    
14. For Each gd In arrGD
    
15.    getRnd = getRnd & gd
    
16. Next
    
17. End Function

复制代码

香川群子

vbaplus 发表于 2013-1-24 21:16
恩，我运用一下洗牌法哈~
要求生成n位随机数，这其中必须包含不重复的1,2,3,4四个数：

你的要求可以更简单地实现。
我的代码只需要随机洗牌排序4次就好了。

原理：
先循环n-4次，生成5-n位的随机字符串，结果为"1234xxxxxxx……"
然后，用经典洗牌法对1-4位进行随机交换，结果就OK啦。
因此，洗牌法的循环次数只有4次。

1. Function RndNum(n%)
   
2.     If n < 4 Then Exit Function
   
3.     s0 = "056789" '除1-4以外，允许随机出现的其它数值合并为字符串变量s0
   
4.     s = "1234" & String(n - 4, "0") '生成目标结果n位数的模板s "123400000……"
   
5.     For i = 5 To n '循环n-4次
   
6.         Mid(s, i, 1) = Mid(s0, Rnd() * 6 + 1, 1) '模板s="1234xxxxx……"
   
7.     Next
   
8.     For i = 1 To 4 '仅对第1-4位的1-4数值进行随机洗牌排序
   
9.         r = Int(Rnd * (n - i + 1)) + i '获取随机位置
   
10.         t = Mid(s, r, 1) '取得结果s中随机位置r的字符存入临时变量t
    
11.         Mid(s, r, 1) = Mid(s, i, 1)  '结果s中随机位置的字符和第i位置的字符进行交换
    
12.         Mid(s, i, 1) = t  '结果s中第i位置写入临时变量中的值（即原来随机位置r的值）
    
13.                                '这样就彻底完成了i位置字符和r位置字符的交换。
    
14.     Next
    
15.     RndNum = s '给函数赋值输出结果
    
16. End Function

复制代码

在这里，直接用mid函数对字符串进行置换操作，计算速度要比数组更快！

vbaplus

香川群子 发表于 2013-1-25 13:08
你的要求可以更简单地实现。
我的代码只需要随机洗牌排序4次就好了。

恩，的确可以只循环4次就够了，我却多循环了n-4次，你每回复一次，我对洗牌的理解就更深一次哈
至于MID对字符串替换为什么比数组快，我还没理解~
是主要快在mid直接替换而不需要数组那么多循环（比如结果输出要循环拼结字符）上？还是说mid处理本身比数组要快？

香川群子

vbaplus 发表于 2013-1-24 21:16
恩，我运用一下洗牌法哈~
要求生成n位随机数，这其中必须包含不重复的1,2,3,4四个数：

你的代码也可以改一下，速度提高不少。

1. Function getRnd1(n%)
   
2.     If n < 4 Then Exit Function
   
3.    
   
4.     Dim i, r%, t%
   
5.     arrRd = Array(0, 5, 6, 7, 8, 9)
   
6.    
   
7.     ReDim arrGD(1 To n)
   
8.     Randomize
   
9.    
   
10.     For i = 1 To 4
    
11.         arrGD(i) = i
    
12.     Next i
    
13.     For i = 5 To n
    
14.         arrGD(i) = arrRd(Int(Rnd * 6))
    
15.     Next i
    
16.     '这里用1-4 和 5-n分开循环赋值的方式。不要每次用If判断。
    
17.    
    
18.     For i = 1 To 4 '这里也只要改成4就可以了
    
19.         r = Int(Rnd * (n - i + 1)) + i
    
20.         t = arrGD(r): arrGD(r) = arrGD(i): arrGD(i) = t
    
21.     Next i
    
22.    
    
23.     getRnd1 = Join(arrGD, "") '这里用join函数可以直接合并数组输出字符串结果。
    
24.    
    
25. End Function
    

复制代码

vbaplus

香川群子 发表于 2013-1-25 13:47
你的代码也可以改一下，速度提高不少。

这里用1-4 和 5-n分开循环赋值的方式。不要每次用If判断。

我之前是这么分开写的，我看行数多，太闹心就写一起了哈，还是你的效率意识比我强，我得多学习。

香川群子

vbaplus 发表于 2013-1-25 13:46
恩，的确可以只循环4次就够了，我却多循环了n-4次，你每回复一次，我对洗牌的理解就更深一次哈
至于MID对 ...

这个应该是这么理解：

向数组内存入数据，肯定比mid置换方法快，差不多要快30%

但是，如果最终结果需要输出为文本字符串时，
把数组结果合并成字符串后输出，要耗费大量时间的。


这个几乎是要比单纯数组循环赋值耗费的时间，多出十倍左右的时间。

因此，如果最终结果是字符串，那么mid方法速度反而要快。


…………
但是，数组尤其是二维、三维数组对算法的好处很大，
这个就不是mid方法可以替代的了。

又由于VBA数组使用时，地址、位置的运算比较容易设计，
所以一般写代码还是喜欢用数组。

但如果计算过程是一维的，内容是文本型值，输出结果还是字符串的话，
显然用mid方法在速度上有绝对的优势。


下面是速度比较代码：

1. Sub test()
   
2.     Dim ii&, run%, n%, s$
   
3.     run = 5
   
4.     n = 100
   
5.    
   
6.    
   
7.     ReDim arrGD(1 To n)
   
8.     tms = Timer
   
9.     For ii = 1 To 10 ^ run
   
10.         For i = 1 To n
    
11.             arrGD(i) = 1
    
12.         Next i
    
13.         's = Join(arrGD, "") '测试时反复体会，把这一句输出字符串结果代码，注释掉和不注释时的时间差别
    
14.     Next
    
15.     MsgBox Format(Timer - tms, "0.0000s")
    
16.    
    
17.     s = String(n, "0")
    
18.     tms = Timer
    
19.     For ii = 1 To 10 ^ run
    
20.         For i = 1 To n
    
21.             Mid(s, i, 1) = "1"
    
22.         Next i
    
23.     Next
    
24.     MsgBox Format(Timer - tms, "0.0000s")
    
25.    
    
26. End Sub

复制代码

ydlpc

顶一个，冒着灌水的风险。

veggieg

香川群子 发表于 2013-1-21 23:47
而你的第2段改写代码，错误更大，已经不能正常运行了。

指针完全错误。

原来这就是LZ说的指针啊.........暴强了....佩服啊 ^^

veggieg

香川群子 发表于 2012-6-20 21:06
占楼。下面是【经典数组洗牌法】实际代码功能扩展的代码例子：

一维数组arr，从其中第a个元素开始，到第 ...

第1次移动后，这个数还在这个位置的概率是1/n，后续移动只会减少这个概率。所以这个算法不是完全随机的

m_n_j001

这就是洗牌嗦？现在才晓得{:soso_e127:}
好象字典那个可以不用remove，速度要快些。