随机和唯一的子集生成

Question

可以说我们有从1到25的数字，我们必须选择15组数字。

可能集，如果我是对3268760.

那些3268760个选项，你必须生成说100000

什么会产生100000独特并随机子集的最佳途径？

有没有一种方法，算法呢？

如果不是，那么检测重复项的最佳选择是什么？

我打算在PHP上这样做，但一般的解决方案就足够了， 和任何不太“学术”（更实用）的参考将会对我有所帮助。

Answer 1

下面是基于MJV的答案，这是我想它在PHP的解决方案。如果你运行一个完整的100k套，你确实会看到很多碰撞。但是，我很难设计一个系统来避免它们。相反，我们只是很快检查它们。

我会考虑更好的解决方案......这台笔记本电脑，我可以做10K在5秒，20K套下20秒。 100k需要几分钟时间。

的集合被表示为（32位）整数。

<?PHP 
    /* (c) 2009 tim - anyone who finds a use for this is very welcome to use it with no restrictions unless they're making a weapon */ 

    //how many sets shall we generate? 
    $gNumSets = 1000; 

    //keep track of collisions, just for fun. 
    $gCollisions = 0; 

    $starttime = time(); 

    /** 
    * Generate and return an integer with exactly 15 of the lower 25 bits set (1) and the other 10 unset (0) 
    */ 
    function genSetHash(){ 
     $hash = pow(2,25)-1; 

     $used = array(); 

     for($i=0;$i<10;){ 

     //pick a bit to turn off 
     $bit = rand(0,24); 

     if (! in_array($bit,$used)){ 
      $hash = ($hash & ~pow(2,$bit)); 
      $i++; 
      $used[] = $bit; 
     } 
     } 
     return $hash; 
    } 

    //we store our solution hashes in here. 
    $solutions = array(); 

    //generate a bunch of solutions. 
    for($i=0;$i<$gNumSets;){ 
     $hash = genSetHash(); 

     //ensure no collisions 
     if (! in_array($hash,$solutions)){ 
     $solutions[] = $hash; 
     //brag a little. 
     echo("Generated $i random sets in " . (time()-$starttime) . " seconds.\n"); 
     $i++; 
     }else { 
     //there was a collision. There will generally be more the longer the process runs. 
     echo "thud.\n"; 
     $gCollisions++; 
     } 
    } 

    // okay, we're done with the hard work. $solutions contains a bunch of 
    // unique, random, ints in the right range. Everything from here on out 
    // is just output. 

    //takes an integer with 25 significant digits, and returns an array of 15 numbers between 1 and 25 
    function hash2set($hash){ 
     $set = array(); 
     for($i=0;$i<24;$i++){ 
     if ($hash & pow(2,$i)){ 
      $set[] = $i+1; 
     } 
     } 
     return $set; 
    } 

    //pretty-print our sets. 
    function formatSet($set){ 
     return "[ " . implode(',',$set) . ']'; 
    } 

    //if we wanted to print them, 
    foreach($solutions as $hash){ 
     echo formatSet(hash2set($hash)) . "\n"; 
    } 

    echo("Generated $gNumSets unique random sets in " . (time()-$starttime) . " seconds.\n"); 

    echo "\n\nDone. $gCollisions collisions.\n"; 

我认为这是正确的，但它是晚了，我一直在享受啤酒几个非常漂亮的瓶子。

Answer 2

他们必须是真正的随机？或者看似随机？

选择：使用Fisher-Yates/Knuth shuffle生成一个包含全部25个集合的集合 - “随机播放”前15个元素，然后检查您是否看过前15个元素的排列。如果是这样，不理会，然后重试。

重复项：您有25个值是否存在 - 这可以简单地散列为整数值（如果存在第一个元素，则添加2^0，如果第二个元素存在，则添加2^1等。 - 它可以直接表示为25位数字），所以你可以很容易地检查，如果你已经看到它。

你会得到碰撞的公平一点，但如果它不是一个性能关键片段，它可能是可行的。

Answer 3

环境中的随机数字生成器（RNG）将为您提供均匀分布在特定范围内的随机数字。这种类型的分布往往需要什么，说如果你的子集模拟彩票图纸，但提到这个事实的情况下，你是建模说的上一所中学的理由，人们发现年龄是很重要的......

鉴于此RNG，您可以“绘制”1到25之间的10（或15，下面读取）数字。这可能需要您将发生器产生的随机数相乘（并舍入），并且忽略大于25的数字（即再次绘制），取决于与RNG相关的确切API，但再次在给定范围内绘制图形并不重要。当数字再次出现时，您还需要重新绘制。

我建议你只得到10号，因为这些可以从1-25完整序列中删除，以产生一组的15换言之绘制15把中是相同的图10取出来......

接下来你需要声明集合的唯一性。您可以使用散列来唯一标识每个集合，而不是存储整个集合。这应该少于25位，所以可以存储在32位整数。然后，您需要拥有高达100,000个这些值的高效存储空间;除非你想把它存储在数据库中。

在取出来的所有可能的集10万套独特的这个问题，发生碰撞的概率似乎相对较低。编辑：哎呀......我很乐观......这个概率并不是很低，大约有1.5％的机会在绘制第5万次之后开始碰撞，所以会有相当多的碰撞，足以保证系统排除它们...

Answer 4

有一种方法来产生是随机的子集，保证不会有重复的样本，使用了O（1）存储，并且在任何时间可被重新生成。首先，写一个函数generate a combination given its lexical index。其次，使用pseudorandom permutation of the first Combin(n, m) integers以随机顺序遍历这些组合。简单地将数字0 ... 100000输入到置换中，使用置换的输出作为组合生成器的输入，并处理结果组合。