4

对于我现在正在处理的问题,我希望从给定集合的幂集中进行合理统一的随机选择。不幸的是,这正好涉及统计数据,这是我根本没有研究过的东西(现在我正在进入真正的编程领域,我需要纠正一些东西)所以我想在一些知道它的人面前运行我的解决方案。

如果给定集合的大小为 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. 我很确定(仅从直观的角度来看)我的方案在子集的大小上提供了统一的选择(相对于子集的总量是统一的。在集合 {1, 2, .., n} 个尺寸)。

  2. 我正在使用一个库(python's random.sample)来获取给定大小的子集,所以我相信这将是统一的。

所以我的问题是,如果按照我所描述的方式将两者放在一起,是否会使随机大小的随机子集的选择变得统一。如果答案是大量工作,那么我很乐意接受有关如何证明这一点并为自己完成工作的指示。另外,如果有更好的方法来做到这一点,那么我当然会对此感到高兴。

4

2 回答 2

9

我认为你会走很长的路。当您提到幂集的大小为 2 n时,您已经很接近了。如果要选择一组 size 的幂集的随机元素,请n在 [0, 2 n ) 范围内生成一个随机整数,并使用整数的二进制表示从幂集中选择适当的元素。

例如,假设 S = {a, b, c, d, e}。那么幂集包含 2 5 = 32 个元素。生成一个从 0 到 31 的随机数,例如 18。18 的二进制表示是 10010,因此您将选择 S 的第一个和第四个元素。您的幂集的随机元素是 {a,d}。

于 2010-10-16T06:00:22.220 回答
3

依次考虑给定集合的每个元素,并以 1/2 的概率决定将其包含在结果集中。

于 2010-10-16T08:12:10.813 回答