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 回答