随机和唯一的子集生成

StackOverflow https://stackoverflow.com/questions/1425184

题

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

如果我是对的，可能的套装是3268760。

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

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

有没有办法，算法可以做到这一点？

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

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

有帮助吗？

解决方案

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

我会考虑更好的解决方案......在这台笔记本电脑上，我可以在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";

我认为这一切都是正确的，但现在已经很晚了，我一直在享用几瓶非常好的啤酒。

其他提示

有一种方法可以生成随机的子集样本，保证不会有重复，使用O（1）存储，并且可以随时重新生成。首先，写一个函数到根据它的词汇生成一个组合指数。其次，使用第一个Combin（n，m）整数的伪随机置换以随机顺序逐步遍历这些组合。只需将数字0 ... 100000输入到排列中，使用排列的输出作为组合生成器的输入，并处理结果组合。

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

选择：生成一个具有全部25 - “shuffle”的集合。前15个元素使用Fisher-Yates / Knuth shuffle，然后检查你是否已经看过前15个元素的排列。如果是这样，请忽略并重试。

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

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

您环境中的随机数生成器（RNG）将为您提供均匀分布在特定范围内的随机数。这种类型的分发通常是需要的，例如，如果你的子集模拟彩票图纸，但重要的是要提到这个事实，以防你的建模说明在中学的基础上发现的人的年龄......

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

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

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top