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

hamtyb

这个找了好久了.谢谢LZ分享经验了！！

pp9257

只能站在门外膜拜一下

wjhere

正在学习随机不重复的方法，先收藏。

wjhere

又学习了一遍，能够看懂了那个最简单的代码了，真的很不错。这种随机不重复抽取的结果是一个数组，在实际运用中需要自己再加工。

vbaplus

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

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

香川，我喜欢看你的帖子~
对于本贴9楼中的问题：
一维数组arr，从其中第a个元素开始，到第b个元素为止的区间内，任意抽取n个不重复值返回。
其中，n<=b-a+1  即n可以正好和a-b中元素个数相等，或小于a-b区间中的元素个数。

你给出的洗牌算法是：

1. Sub GetRnd(arr, a, b, n)
   
2.     Randomize
   
3.     l = LBound(arr)
   
4.     For i = l To n + l - 1 '正序洗牌
   
5.         r = Int(Rnd() * (b - a + 1 - (i - l))) + a + (i - l)
   
6.         t = arr(r, 1)
   
7.         arr(r, 1) = arr(i + a - l, 1)
   
8.         arr(i, 1) = t '下标1开始一维代码
   
9.     Next
   
10. End Sub

复制代码

这里我有点不理解的是，arr(r)为什么要用 arr(i + a - l)填充？
像如下两种写法应该也是满足要求的，你是不是有别的什么用意？

1. Sub GetRnd(arr, a, b, n)
   
2.     Randomize
   
3.     s = LBound(arr)
   
4.     For i = s To n + s - 1 '正序洗牌
   
5.         r = Int(Rnd() * (b - a + 1 - (i - s))) + a + (i - s)
   
6.         t = arr(r, 1)
   
7.         arr(r, 1) = arr(i, 1)
   
8.         arr(i, 1) = t '下标1开始一维代码
   
9.     Next
   
10. End Sub

复制代码

1. Sub GetRnd(arr, a, b, n)
   
2.     Randomize
   
3.     s = LBound(arr)
   
4.     For i = 1 To n '正序洗牌
   
5.         r = Int(Rnd() * (b - a - i + 1)) + a + i
   
6.         t = arr(r + s - 1, 1)
   
7.         arr(r + s - 1, 1) = arr(i + s - 1, 1)
   
8.         arr(i + s - 1, 1) = t '下标1开始一维代码
   
9.     Next
   
10. End Sub

复制代码

香川群子

vbaplus 发表于 2013-1-21 15:03
香川，我喜欢看你的帖子~
对于本贴9楼中的问题：
一维数组arr，从其中第a个元素开始，到第b个元素为止的 ...

关于第一个问题：

你例子中，用arr(i, 1)来代替我代码中的arr(i + a - l, 1) 【你自己的习惯是arr(i + a - s, 1)】

那么，如果a=l或者说a=s的时候，当然两个式子的结果是等价的。

但如果a不是从l或s开始，而是l+2或l+5开始呢？

显然两者就不同了。

………

要点：
我的代码，起始位置可以任意指定。

举例：数组元素1-10，我可以：
  指定a=1、b=10、n=10，即从1-10中随机抽取10个并返回全部10个元素。
或指定a=1、b=10、n=6，即从1-10中随机抽取6个后就结束，后面剩余4个元素不管了。

或指定a=3、b=10、n=4，即从3-10中随机抽取4个后就结束，
那么抽取到的4个数肯定不会含1、2，而且一共还剩余6个元素不用管了。


或指定a=3、b=8、n=4，即从3-8中随机抽取4个后就结束，
那么抽取到的4个数肯定既不会含1、2，也不会含9、10，而且一共还剩余6个元素不用管了。


就是这个意思。

而你改写的代码，就做不到了。

香川群子

vbaplus 发表于 2013-1-21 15:03
香川，我喜欢看你的帖子~
对于本贴9楼中的问题：
一维数组arr，从其中第a个元素开始，到第b个元素为止的 ...

而你的第2段改写代码，错误更大，已经不能正常运行了。

指针完全错误。

vbaplus

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

指针完全错误。

恩，谢谢，香川，我的两段改写应该都是错在没有理解arr(r, 1) = arr(i + a - l, 1)造成的。我的改写错在：我用从arr最开始的位置按顺利取值去填充arr(r,1)，而这个随机取值位置还有被再次取值的可能，如果被再次取到的话，那就出现arr最初位置的数据，不符合在a~b位置取值的条件。而你用arr(i + a - l, 1)去填充arr(r, 1) ，也就是在 a~b区间上从第一个位置开始取值去填充arr(r,1)随机取值位，而不是像我那样从arr的最初位置去取值填充，这样做就避免了我刚才犯的错误，你处理得很完美。

经过这次理解，我再重新改写了一下，你看还有没有错误？另外我把你的l改为s是因为l和1有视觉混淆。

1. Sub GetRnd(arr, a, b, n)
   
2.     Randomize
   
3.     s = LBound(arr)
   
4.     For i = 1 To n '正序洗牌
   
5.         r = Int(Rnd() * (b - a - i + 1)) + a + i
   
6.         t = arr(r + s - 1, 1)
   
7.         arr(r + s - 1, 1) = arr(i + a - 1, 1)
   
8.         arr(i + s - 1, 1) = t '下标1开始一维代码
   
9.     Next

复制代码

香川群子

vbaplus 发表于 2013-1-22 20:42
恩，谢谢，香川，我的两段改写应该都是错在没有理解arr(r, 1) = arr(i + a - l, 1)造成的。我的改写错在： ...

呵呵，而我就是故意用小写l作为参数，让粗心的人以为是1……

只有真正理解代码的人才不会搞错。

香川群子

vbaplus 发表于 2013-1-22 20:42
恩，谢谢，香川，我的两段改写应该都是错在没有理解arr(r, 1) = arr(i + a - l, 1)造成的。我的改写错在： ...

理论上，如果每次a都比起始位置大，那么交换只要两次就可以了，不用回填到 i + a - l 位置了。

不过，因为实际上偏偏a=起始位置的情形是最容易出现的，所以通用代码就只能牺牲一点速度了。