0

{1,...,n} から m 個の要素のサブセットをランダムに選択するこの短いプログラムを作成しました -

std::set<int> randSubSet(int n, int m){
  // generates a random subset of m elements from {1,...,n} uniformly

  if (m>n) //check inputs validity
    throw std::invalid_argument("m is larger then n.");

  std::set<int> res{}; //initialize result set

  if (m==n){ //easy case - the full set
     for(int i = 1 ; i<n ; ++i)
         res.insert(i);
  }

  std::mt19937 eng;
  std::uniform_int_distribution<> uni(1,n);

  if ( m == 0 ){ // recursion base case

      return res;
  }
  else {
      res = randSubSet(n-1,m-1);
      int i = uni(eng);
      if (res.find(i) == res.end()) // if i isn't in S add it
          res.insert(i);
      else
          res.insert(n); //else add n

  }
  return res;
}

eng はシードされていないため、常に同じ答えが得られます。このシナリオで eng をシードするにはどうすればよいですか? (各呼び出しには独自のエンジンがあるため)

グローバル変数を使用して問題を回避できます。より良い解決策があるかどうか疑問に思っていました。ありがとう！

4

2 に答える 2

2

すべての再帰ステップで同じエンジンが使用されるように、ランダム エンジンを引数として関数に渡すことができます。関数のシグネチャは になりstd::set<int> randSubSet(int n, int m, std::mt19937& eng)ます。次に、関数を使用するためにランダム エンジンを渡す必要があるため、ランダム エンジンを使用しないオーバーロードを作成し、デフォルトのランダム エンジンを使用して関数を呼び出すことができます (現在と同じ方法で構築されます)。 ）。

于 2013-09-28T06:16:28.433 に答える
0

再帰関数を「シード」する簡単な方法は、非再帰関数でラップすることです。セットアップを行う非再帰関数を記述し、再帰関数を呼び出してジョブを実行するだけです。

意味のある別の方法は、デフォルトのinit=trueパラメーターを使用することです。再帰関数内で、自分自身をinit=false.

于 2013-09-28T06:18:40.753 に答える