高效枚举具有常和的多项式 - R

Question

假设我有一个 N 面骰子，每一面的概率不均匀，我将其扔了 M 次。现在我们不再观察个体结果，而是只观察总和。

我必须对可能性进行编码，其中我必须对仅限于观察到的总和的多项可能性分量进行求和。

如果 N=3，M = 2 并且总和为 4，那么很明显，我必须对其中一个投掷为 1、另一个投掷为 3 的两种情况加上两者均为 2 的情况进行求和。

我还可以枚举所有可能性，计算总和并将计算限制为我感兴趣的总和的组合，但显然随着 N 和 M 的增加，这很快就会变得棘手。

所以我正在寻找一种有效的方法来选择 R 中的常和组合。

Answer 1

一种选择是使用RcppAlgos::compositionsGeneral()“在各种约束下对数字进行分区的有效算法”。

library(RcppAlgos)

compositionsGeneral(3, 2, repetition = TRUE, target = 4)

     [,1] [,2]
[1,]    1    3
[2,]    2    2
[3,]    3    1

正如 @ThomasIsCoding 所指出的，这种方法可能会失败并显示以下消息：

compositionsGeneral(3, 6, repetition = TRUE, target = 10)

Error: Currently, there is no composition algorithm for this case.
 Use permuteCount, permuteIter, permuteGeneral, permuteSample, or
 permuteRank instead.

因此，为了解决这个问题，我们可以捕获错误并permuteGeneral()依靠此事件中的约束：

comps <- \(v, m, x) {
  tryCatch(
    compositionsGeneral(v,
                        m,
                        repetition = TRUE,
                        target = x),
    error = function(e)
      permuteGeneral(v,
                     m,
                     repetition = TRUE,
                     constraintFun = "sum",
                     comparisonFun = "==",
                     limitConstraints = x
      )
  )
}


comps(3, 6, 10)

      [,1] [,2] [,3] [,4] [,5] [,6]
 [1,]    1    1    1    1    3    3
 [2,]    1    1    1    3    1    3
 [3,]    1    1    1    3    3    1
 [4,]    1    1    3    1    1    3
 [5,]    1    1    3    1    3    1
...
[85,]    2    2    1    1    2    2
[86,]    2    2    1    2    1    2
[87,]    2    2    1    2    2    1
[88,]    2    2    2    1    1    2
[89,]    2    2    2    1    2    1
[90,]    2    2    2    2    1    1

请注意，该文档包含以下有关计算带约束的排列的内容：

通过以这样的方式组织它们来优化寻找具有约束的所有组合/排列：当应用constraintFun时，产生部分单调序列。连续添加组合/排列，直到特定组合超过给定约束/比较函数组合的给定约束值。在此之后，我们可以安全地跳过几个组合，因为知道它们将超过给定的约束值。