4

假设我们有从 1 到 25 的数字，我们必须选择 15 个数字的集合。

如果我是对的，可能的集合是 3268760。

在这 3268760 个选项中，您必须生成 100000 个

生成 100000 个唯一且随机的子集的最佳方法是什么？

有没有办法，一种算法来做到这一点？

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

我打算在 PHP 上执行此操作，但一个通用的解决方案就足够了，任何不涉及太多“学术”（更实用）的参考都会对我有很大帮助。

4

4 回答 4

4

有一种方法可以生成随机的子集样本，保证没有重复，使用 O(1) 存储，并且可以随时重新生成。首先，编写一个函数来生成一个给定词法索引的组合。其次，使用第一个 Combin(n, m) 整数的伪随机排列以随机顺序逐步遍历这些组合。只需将数字 0...100000 输入到排列中，使用排列的输出作为组合生成器的输入，然后处理结果组合。

于 2009-09-15T06:16:31.957 回答
2

它们必须是真正随机的吗？还是看似随机？

选择：生成一个包含所有 25 个元素的集合 - 使用 Fisher-Yates / Knuth 洗牌“洗牌”前 15 个元素，然后检查您之前是否见过前 15 个元素的排列。如果是这样，请忽略并重试。

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

你会遇到相当多的冲突，但如果它不是性能关键的片段，它可能是可行的。

于 2009-09-15T05:25:26.333 回答
2

您环境的随机数生成器 (RNG) 将为您提供均匀分布在特定范围内的随机数。这种类型的分布通常是需要的，例如，如果您的子集模拟彩票抽奖，但重要的是要提及这一事实，以防您在建模时说在中学范围内发现的人的年龄......

鉴于此 RNG，您可以“绘制” 10（或 15，请阅读下文）介于 1 和 25 之间的数字。这可能需要您乘以（并四舍五入）生成器产生的随机数，并且忽略大于 25 的数字（即再次绘制），这取决于与 RNG 关联的确切 API，但再次在给定范围内获取绘图是微不足道的。当数字再次出现时，您还需要重新绘制。

我建议您只获取 10 个数字，因为这些可以从 1-25 完整序列中删除以产生一组 15。换句话说，放入 15 的绘图与取出的 10 相同...

接下来，您需要断言集合的唯一性。您可以使用散列来唯一标识每个集合，而不是存储整个集合。这应该占用少于 25 位，因此可以存储在 32 位整数上。然后，您需要高效存储多达 100,000 个这些值；除非您想将其存储在数据库中。

在这个从所有可能的集合中取出 100,000 个集合的唯一性问题上，碰撞的概率似乎相对较低。编辑：哎呀...我很乐观...这个概率不是那么低，大约有 1.5% 的机会在绘制第 50,000 个之后开始发生碰撞，会有相当多的碰撞，足以保证系统将它们排除在外...

于 2009-09-15T05:34:32.837 回答
2

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

我会考虑更好的解决方案……在这台笔记本电脑上，我可以在 5 秒内完成 10k 套，在 20 秒内完成 20k 套。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";

我认为这一切都是正确的，但为时已晚，我一直在享用几瓶非常棒的啤酒。

于 2009-09-15T08:02:11.180 回答