c++ - 如何播种递归 C++ 函数

Question

我编写了这个简短的程序来从 {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？（因为每个调用都有自己的引擎）

我可以使用全局变量来避免这个问题，我想知道是否有更好的解决方案。谢谢！

Answer 1

您可以将随机引擎作为参数传递给函数，以便在每个递归步骤中使用相同的引擎。您的函数的签名将变为std::set<int> randSubSet(int n, int m, std::mt19937& eng). 然后，您需要传递一个随机引擎才能使用该函数，因此您可以创建一个不采用随机引擎的重载，并使用默认随机引擎调用您的函数（以与您现在相同的方式构建）。

Answer 2

让递归函数“播种”的简单方法是将其包装在非递归函数中：您只需编写一个非递归函数来进行设置，然后调用递归函数来完成这项工作。

一种可能有意义的替代方法是使用默认init=true参数：在递归函数中，您称自己为传递init=false。