r - 处理 R 中的递归深度限制

Question

算法来自https://www.math.upenn.edu/~wilf/eastwest.pdf第 16 页 RandomKSubsets

RandomKSubsets = function(n, k){
  if (n<0 | k<0 | k<n){
    return()
  }
  else {
    if (n==0 && k==0){
      return(c())
    }
    else {
      rno = runif(1)
      if (rno < n/k){
        east = RandomKSubsets(n-1,k-1)
        return (c(east, k))
      }
      else{
        west = RandomKSubsets(n,k-1)
        return(west)
      }
    }
  }
}

在 k=4000 和 n=1200 的情况下运行程序，我遇到了递归深度限制。我尝试了 options(expressions=500000) 但这对算法来说还不够。如何为我的变量运行此代码？

Answer 1

这接近于尾递归:唯一的递归调用是在 return 语句中。此博客:http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html描述了如何将此类函数更改为循环。我遵循了那里描述的大部分机械过程，并提出了这个版本:

RandomKSubsetsLoop = function(n, k) {
  acc <- NULL
  while (TRUE) {
    if (n<0 | k<0 | k<n){
      return(acc)
    }
    else {
      if (n==0 && k==0){
        return(acc)
      }
      else {
        rno = runif(1)
        if (rno < n/k){
          acc <- c(k, acc)
          k <- k - 1
          n <- n - 1
          next
        }
        else{
          k <- k - 1
          next
        }
      }
    }
    break
  }
}

我没有对它进行广泛的测试，但它产生的结果与本次测试中的原始结果相同:

set.seed(1)
RandomKSubsets(5, 10)
# [1]  1  3  6  9 10
set.seed(1)
RandomKSubsetsLoop(5, 10)
# [1]  1  3  6  9 10

您可能想要进行更广泛的测试，并阅读博客以确保我已经按照它描述的那样做了事情。

顺便说一句，还有其他算法可以进行这种采样，例如

中描述的那个

AUTHOR="McLeod, A.I. and Bellhouse, D.R. ",
YEAR = 1983,
TITLE="A convenient algorithm for drawing a simple random sample",
JOURNAL="Applied Statistics",
VOLUME="32",
PAGES="182-184"

那个是基于循环设计的，优点是你不需要提前知道总体规模(k 在你的符号中):你只需要不断更新你的样本直到没有更多的项目要处理。