如何获得 R 中所有可能的组合?

机器算法验证 r 非参数 组合学
2022-04-07 02:47:41

有时我想通过检查数据的所有可能组合来进行精确测试,以建立一个经验分布,我可以根据该分布来测试我观察到的平均值之间的差异。为了找到可能的组合,我通常会使用 combn 函数。选择功能可以告诉我有多少种可能的组合。组合的数量很容易变得如此之大,以至于无法存储 combn 函数的结果,例如 combn(28,14) 需要 2.1 Gb 的向量。因此,我尝试编写一个对象,该对象单步执行与 combn 函数相同的逻辑,以便一次提供一个虚构的“堆栈”中的值。但是,这种方法(正如我实例化的那样)在合理的组合大小下很容易比 combn 慢 50 倍,

有没有比 combn 中使用的算法更好的算法来做这种事情?具体来说,有没有一种方法可以生成和提取第 N 个可能的组合,而无需计算所有先前的组合?

2个回答

如果您希望以处理速度换取内存(我认为您会这样做),我建议您使用以下算法:

  • 设置一个从 1 到 N 的循环 选择 K,索引为 i
  • 每个 i 都可以被认为是组合的索引,因此解码
  • 使用组合来执行您的测试统计,存储结果,丢弃组合
  • 重复

这将为您提供所有 N 选择 K 种可能的组合,而无需显式创建它们。如果您愿意,我有代码可以在 R 中执行此操作(您可以通过 mark dot m period fredrickson at-symbol gmail dot com 给我发电子邮件)。

生成组合很容易,例如看这个在 R 中编写此代码,然后一次处理每个组合。