aar*_*ing 4 random algorithm math statistics powerset
对于我现在正在处理的问题,我希望从给定集合的powerset中选择一个相当统一的随机选择.不幸的是,这直接进入统计数据,这是我根本没有研究过的东西(我现在需要纠正的是我正在进行真正的编程)所以我想通过一些了解它的人来运行我的解决方案.
如果给定集合的大小为n,则存在大小为k的(nk)= n!/ [k!(nk)!]子集,并且赋予powerset的总大小N作为k上的(nk)之和0到n.(也给出了2 n,但我不认为这有用.我可能显然是错的).
所以我的计划是将[0,1]分区为以下区间:
[0, (n 0)/N]
((n 0)/N, [(n 0) + (n 1)]/N]
([(n 0) + (n 1)]/N, [(n 0) + (n 1) + (n 2)]/N]
...
([N - (n n)]/N, 1]
在算法上,通过将前一个区间的最大元素作为新区间的最大下限加上(nj)/ N来获得最大元素来构造区间.我希望这很清楚.
然后我可以通过在[0,1]中选择一个统一浮点并将其映射到它所属的区间的索引来计算出随机子集中有多少个元素.从那里,我可以选择适当大小的随机子集.
我非常肯定(从一个直观的角度来看)我的方案提供了一个关于子集大小的统一选择(相对于子集总量的统一.它在集合{1,2,...上显然不均匀) n}尺寸).
我正在使用一个库(python's random.sample)来获取给定大小的子集,所以我相信这将是统一的.
所以我的问题是如果以我描述的方式将两者组合在一起,就可以选择随机大小的随机子集.如果答案很多,那么我很高兴接受关于如何证明这一点并指导我自己的工作的指示.此外,如果有更好的方法来做到这一点,那么我当然会对此感到满意.
我想你会走很长的路.当你提到功率设置的大小为2 n时,你很接近.如果要选择一组大小的幂集的随机元素n,请生成[0,2 n ] 范围内的随机整数,并使用整数的二进制表示从电源集中选择适当的元素.
例如,假设S = {a,b,c,d,e}.然后,功率组包含2 5 = 32个元素.生成从0到31的随机数,例如18. 18的二进制表示是10010,因此您将选择S的第一个和第四个元素.然后,幂集的随机元素为{a,d}.