随机生成一个子集？

这是一个组合算法的implementation，可以随机均匀地选择一个n集的一个子集。由于有n个集合的子集，每个子集应该有一个概率：2 ^-n被选中。随机生成一个子集？

我相信我已经正确实施了算法（请让我知道是否有错误的地方）。但是，当我在Linux机器上使用Java 7运行程序时，我得到的结果不能很好地解释。神秘似乎围绕着随机数发生器。我明白，需要运行程序“大量”来“看到分布达到统一”。然而问题是多大是多大。我确实提出了几次试验，除非实验完成的次数> 10亿次，否则所选子集的分布是非常不均匀的。

该算法基于Herbert Wilf教授的组合算法书，其中实现（略有不同）是在Fortran中完成的，即使程序仅运行1280次，分布也差不多均匀。

这里有几个样品运行（有运行中的一些变化，当n为常数）得到4组的随机子集：

次实验的号码是否做过N = 1280
次实验的号码是否做过N = 12,800
次实验的号码是否做过N = 128,000（仍仅为8子集！）
次实验的号码是否做过N = 1,280,000
次实验的号码是否做过N = 12,800,000（现在它开始决策意识）
次实验的号码是否做过N = 1,280,000,000（这是好的！）

，你会期望这样的表现？ Wilf教授如何才能实现类似的结果，只有迭代的等效程序？

来源

2014-09-25 Kedar Mhaswade

每次拨打ranInt()时，都会重置RNG。因此，从长远来看，这些数字不再是随机的。
感动Random r = new Random(System.currentTimeMillis());顶端，并添加static它

class RandomSubsetSimulation { 
    static Random r = new Random(System.currentTimeMillis()); 
    public static void main(String[] args) { ...

我能够用8集

Total: 1000, number of subsets with a frequency > 0: 256 
Total # of subsets possible: 256

全部结果有4套，以得到下面的结果

Frequencies of chosen subsets .... 
       [3] :   76,   4, 5.94 
       [4] :   72,   8, 5.63 
        [] :   83,   -3, 6.48 
       [1] :   90,  -10, 7.03 
       [2] :   80,   0, 6.25 
       [3, 4] :   86,   -6, 6.72 
       [2, 3] :   88,   -8, 6.88 
       [2, 4] :   55,   25, 4.30 
      [1, 2, 3] :   99,  -19, 7.73 
      [1, 2, 4] :   75,   5, 5.86 
      [2, 3, 4] :   76,   4, 5.94 
       [1, 3] :   85,   -5, 6.64 
       [1, 2] :   94,  -14, 7.34 
       [1, 4] :   72,   8, 5.63 
     [1, 2, 3, 4] :   71,   9, 5.55 
      [1, 3, 4] :   78,   2, 6.09 
Total: 1280, number of subsets with a frequency > 0: 16 
Total # of subsets possible: 16

来源

2014-09-25 23:09:37 Steven

谢谢@Steven。这是一个愚蠢的错误:-)。 – 2014-09-25 23:20:49

修复了原始代码[here]（https://gist.github.com/kedarmhaswade/c5ad394d0058d6965f6e#file-randomsubsetsimulation-java-L52） – 2014-09-26 01:38:25

随机生成一个子集？

回答

相关问题