随机选取无重复元素子集合，我写了几种算法的证明，这些证明有没有错误呢
诚惶诚恐受邀。多年不做算术题了，而且算术一直是弱项，如果下面计算有错还请指正、轻拍。虽然说蛇年到了打算学一下Python，但是看着题主的代码然后一边查一边学试着写，也没能写出能用的代码，只停留在能看懂题主代码的程度。所以关于那些算法的测试，我是使用Ruby重写了一遍然后测的。言归正传，先说说关于这些算法测试吧。测试的代码主要针对三项指标：结果种类、结果方差和运行时间。对结果的种类计数，验证正确性；对每一种结果的数量进行统计，看是不是每一种都是等概率；计算运行时间，看看性能表现。代码（Ruby）如下：def test func, times=1_000_000, n=5, m=5\tputs "Testing #{func.name}, n = #{n}, m = #{m}, #{times} times"\tresult = {} # 定义一个字典，用于存放结果\tt1 = Time.now\ttimes.times do |x| # 重复进行1000000次\t\ta = func.call(n,m) # 调用测试函数\t\tif nil == result then\t\t\tresult = 1\t\telse\t\t\tresult += 1\t\tend\t\tprint "." if x % (times/50) == 0\tend\tt2 = Time.now\tputs nil\tr, avg = analyze(result.values, times, result.length) # 统计结果\tputs " #{result.length}/#{combine(n, m)} results, #{"%.6f" % r}, #{"%.6f"%(100*r/avg)}%"end运行之后得到这样的结果（运行多次观察选取了一个有代表性的）：Testing algo1, n = 9, m = 5, 1000000 times.................................................. 126/126 results, 103.632562, 1.305770%Testing algo2, n = 9, m = 5, 1000000 times.................................................. 126/126 results, 82.761222, 1.042791%Testing algo3, n = 9, m = 5, 1000000 times.................................................. 126/126 results, 90.688191, 1.142671%Testing algo4, n = 9, m = 5, 1000000 times.................................................. 126/126 results, 90.053739, 1.134677%上面结果表明，四种算法都是正确的，而且生成的结果也比较均匀，时间上略有一些差别，其中算法四最快。算法一：这个算法原理很简单，也没有什么太大的问题，就是计算的时候，题主采取了一个比较麻烦的做法，最后的结果应该是出了一点小小的错误。这个题目的证明其实比较简单，对于第i次抽取，已经抽取了i-1个元素，剩余n-i+1个（也就是题主博客中的n-t），所以抽中没有抽过的元素的概率为
。不断的抽取直到抽到没有抽过的元素，这样是试验概率是服从几何分布，所以数学期望有公式直接得到
，所以总抽取次数的数学期望为
。算法二：这个算法的原理也很简单，证明过程也很简单。理论上表现会比算法一要好一点。而实际性能却比算法一要慢不少，经过分析觉得受到两个容器的影响比较大，辅助的数组的插入和移除操作应该相当耗时。算法三：这个算法就比较巧妙了，递归地去解决这个问题：从n个元素的集合中选取m个元素，每个元素被选到的概率都是
；问题变为，有
的概率抽取第一个元素，然后在从剩下的元素中抽取m-1个元素，或者有 【随机选取无重复元素子集合，我写了几种算法的证明，这些证明有没有错误呢】
推荐阅读
- |淮阴水政充分利用“双随机”平台 促进执法公平公正
- 论开源软件的利弊有哪些
- 可以通过伪随机生成真实的地球吗
- 数独设计的原理是啥
- 随机森林和logistics回归性能比较。logistics \u003e randomforest ?
- 怎样正确解读《有 100 人，每人有 100 块，随机给一个人 1 块，最后钱分布怎么样》的运行结果
- 怎样避免无状态的RESTful中订单的重复提交
- raw处理软件是怎样从14位的raw图像中选取最终呈现的那8位的部分
- 炉石传说开包用的啥伪随机算法
- 咋在重复的功能测试中学习到更多东西求解答