对于我现在正在处理的问题,我希望从给定集合的幂集中进行合理统一的随机选择。不幸的是,这正好涉及统计数据,这是我根本没有研究过的东西(现在我正在进入真正的编程领域,我需要纠正一些东西)所以我想在一些知道它的人面前运行我的解决方案。
如果给定集合的大小为 n,则有 (nk) = n!/[k!(nk)!] 个大小为 k 的子集,并且幂集的总大小 N 为 (nk) 与 k 的总和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
)来获取给定大小的子集,所以我相信这将是统一的。
所以我的问题是,如果按照我所描述的方式将两者放在一起,是否会使随机大小的随机子集的选择变得统一。如果答案是大量工作,那么我很乐意接受有关如何证明这一点并为自己完成工作的指示。另外,如果有更好的方法来做到这一点,那么我当然会对此感到高兴。