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

これがmjvの答えに基づいたPHPの解決策であり、それが私がそれについて考えていた方法です。完全な100kセットで実行すると、実際に多くの衝突が発生します。しかし、私はそれらを回避するためのシステムを考案することを強く求められています。代わりに、かなり迅速にチェックします。

より良い解決策を考えます...このラップトップでは、5秒で10kセット、20秒未満で20kセットを実行できます。100kには数分かかります。

セットは（32ビット）intとして表されます。 

<?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 に答える
2

それらは本当にランダムである必要がありますか? それとも一見ランダム？

選択: 25 個すべてのセットを生成します。Fisher-Yates / Knuth シャッフルを使用して最初の 15 要素を「シャッフル」し、最初の 15 要素の順列を以前に見たことがあるかどうかを確認します。その場合は、無視して再試行してください。

重複: 存在するかどうかに関係なく 25 個の値があります - これは簡単に整数値にハッシュできます (最初の要素が存在する場合は 2^0 を追加し、2 番目の要素が存在する場合は 2^1 を追加します。 25 ビットの数値として直接表現されているため、既に見たことがある場合は簡単に確認できます。

かなりの衝突が発生しますが、パフォーマンスが重要なスニペットでない場合は、実行できる可能性があります。

于 2009-09-15T05:25:26.333 に答える
2

環境の乱数ジェネレーター (RNG) は、特定の範囲に均等に分散された乱数を提供します。このタイプの分布は、サブセットが宝くじの抽選をシミュレートする場合などに必要になることがよくありますが、中学校の敷地内で見つかった人々の年齢などをモデル化する場合に備えて、この事実に言及することが重要です...

この RNG を指定すると、1 から 25 までの 10 (または 15、以下を参照) の数値を「描く」ことができます。これには、ジェネレーターによって生成された乱数を乗算 (および四捨五入) し、25 を超える数値を無視する必要がある場合があります ( RNG に関連付けられた正確な API によって異なりますが、指定された範囲で描画を取得するのは簡単です。また、数字が再び出てきたときに再描画する必要があります。

これらは 1 ～ 25 の完全なシーケンスから削除して 15 のセットを生成できるため、10 の数字のみを取得することをお勧めします。

次に、セットの一意性を主張する必要があります。セット全体を保存するのではなく、ハッシュを使用して各セットを一意に識別できます。これは 25 ビット未満で済むため、32 ビットの整数に格納できます。次に、これらの値を最大 100,000 個格納できる効率的なストレージが必要です。これをデータベースに保存する場合を除きます。

考えられるすべてのセットから取り出した 100,000 セットの一意性に関するこの問題では、衝突の可能性は比較的低いようです。編集：おっと...私は楽観的でした...この確率はそれほど低くはありません。50,000番目を描画した後に衝突が始まる可能性は約1.5％です。かなりの数の衝突があり、それらを除外するシステムを保証するのに十分です...

于 2009-09-15T05:34:32.837 に答える