使用替换获取特定组合

Question

我知道如何计算有替换情况下从n个不同物体中取k个物体的所有组合数：

(n+k-1)!/k!/(n-1)!

我需要的是一个公式或算法，可以从有序列表中恢复第i个这样的组合。

假设我有一个由a、b、c三个元素中取3个元素得到的所有组合的有序列表（因此n=3且k=3）：

1 aaa 2 aab 3 aac 4 abb 5 abc 6 acc 7 bbb 8 bbc 9 bcc 10 ccc

在不列举所有组合的情况下，我该如何计算这个列表中的第i个组合（如第7个）？如果我只对一些特定的组合感兴趣，那么枚举将非常低效。例如，有64个项目，每次取6个项目，有119,877,472种组合方式。

不用说，我需要一个适用于任意n、k和i的解决方案。反向函数（给定组合，如何计算其索引）也很有趣。

我找到了一个类似的问题，但它是关于排列而不是组合的： I want to get a specific combination of permutation? 还有许多列出所有组合的方法，例如这里提到的： How to generate all permutations and combinations with/without replacement for distinct items and non distinct items (multisets) 但它们没有给出我需要的函数。

- RoelandV

---

你需要展示你尝试过的代码才能得到任何帮助。 - Eoin

Answer 1

你感兴趣的算法非常容易实现。你首先应该理解的是为什么C(k, n + k - 1) = C(n - 1, n + k - 1) = (n + k - 1)! / k! / (n - 1)! 公式有效。这个公式表明，从n个物品中取出k个物品的方式数与从n个物品中取出n-k个物品的方式数相同。

假设您的对象是某种颜色的球。有n种不同的颜色，编号为1到n。您需要计算拥有k个球的方法数。想象一下最初有k个白球（没有任何颜色），因此您需要以不同的方式将它们涂色。将球排成一行。从左边选择一些k₁ ≥ 0个球涂上颜色＃1，接下来涂上k₂ ≥ 0个球的颜色＃2，依此类推... 我们有∑k_i = k。一系列k₁个颜色为＃1的球，后面跟着k₂个颜色为＃2的球，接下来是k₃个颜色为＃3的球等等...

我们可以以稍微不同的方式完成相同的绘画。为了区分k_i-1和k_i着色的球，我们将使用分隔符。总共应该有n - 1个这样的分隔符放置在球之间。这些分隔符是有序的，一个将1着色和2着色的球分开的分隔符应该出现在另一个将2着色和3着色的球分开的分隔符之前。如果一些k_i = 0，则相应的分隔符一个接一个地出现。我们必须以某种方式排列分隔符和球。

有趣的是，我们现在可以想象，无论n - 1个分隔符和k个球都只是最初放置在一排中的对象。我们必须选择要么声明选定的对象为分隔符，要么将k个对象作为球。这就是著名的组合公式可以应用的地方。

---

您的情况示例：

o - 球
. - 分隔符
a，b，c - 颜色

我们有：
ooo.. => aaa
oo.o. => aab
oo..o => aac
o.oo. => abb
o.o.o => abc
o..oo => acc
.ooo. => bbb
.oo.o => bbc
.o.oo => bcc
..ooo => ccc

请注意分隔符如何从右向左移动的模式。

---

算法

现在来看如何得到第p个排列。下面是高效的算法描述。记住我们有k个球和nd = n - 1个分界符。我们将先一个一个地放置分界符，首先尝试它们最右边的位置。考虑让当前分界符保持在其当前位置，计算将剩余对象放置到右边的组合数，假设该数为N。将N与p进行比较，如果p大于或等于N，则将p减去N（p <- p - N），并且我们应该将当前分界符向左移动1个位置。否则，如果p小于N，则我们不会移动当前分界符，而是继续尝试从最右边的位置再次移动下一个分界符。请注意，第p个排列是从0开始计数的。

将第i个对象“转换”为第j个分隔符后，我们有N = C(nd - j, nd + k - i)种方法来排列剩余的k-i+j个球和nd-j个分隔符。

由于我们经常引用二项式系数，最好预先计算它们。

相应地可以实现反向函数。您拥有每个分隔符的位置。在从最右边的位置将普通分隔符移动到其位置时，累积排列剩余对象的方法数。

例子：

3个球，2个分隔符，找到第7个排列（即bbc或.oo.o）

将分隔符放置在最右侧：ooo..。让第一个分隔符成为当前分隔符。

计算 N = C(1, 1) = 1，p ≥ N，因此我们将p减去N得到p = 6。同时，我们将current分隔符向左移动1个位置，得到oo.o.。

计算 N = C(1, 2) = 2，p ≥ N，减少p的值N得到p = 6 - 2 = 4。移动后得到o.oo.。

再次计算 N = C(1, 3) = 3，p ≥ N，移动并减少p的值，得到p = 1和.ooo.。

计算 N = C(1,4) = 4，p < N。好的，我们已经找到了第一个分隔符的最终位置，所以将其留在那里并将第二个分隔符作为current。

计算 N = C(0,0) = 1，p ≥ N，p = 1 - 1 = 0，移动，.oo.o。

计算 N = C(0,1) = 1，p < N，找到第二个分隔符的最终位置。结果排列为.oo.o => bbc。 编辑 #1。 更改了算法描述并添加了示例。

- Ivan Gritsenko

---

感谢您清晰地解释了带替换的组合计算。然而，该算法仍然存在问题（例如，移动最后一个分隔符对N没有影响，因为总是只剩下1个组合）。我正在努力解决这个问题，我会告诉您我的结果。 - RoelandV

@RoelandV，你说得非常正确，即最后一个分隔符总是留下一种方法来安排右侧的对象。这就是算法中的N。假设你有nb个球在右边，没有分隔符需要安排，那么N = C(0, nb) = 1。在这种情况下，根据算法，你只需将p减1即可。 - Ivan Gritsenko

@RoelandV，请查看我的算法更正和示例。我已经编辑了算法部分第一段的第四句话。这很重要。 - Ivan Gritsenko

根据Ivan的描述，这里是一个（R语言）函数，它以分隔符的位置返回所需的组合。 - RoelandV

Answer 2

这里是函数（尚未优化但可用）：

findcomb <- function(n, k, p) {
  # n = nr of object types (colors, letters etc)
  # k = number of objects (balls) to select
  # p = 0-based index of target combination
  # return = positions of delimiters at index p
  nd <- n-1 #nr of delimiters: 1 - nr of colors
  pos <- seq(n+k-nd, n+k-1) #original positions of delimiters, all at right
  for (j in 1:(nd-1)) {
    s <- 0 #cumulative nr of accounted-for combinations with this delimiter
    while (TRUE) {
      N <- choose(nd+k-pos[j], nd-j)
      if (s + N <= p) {
        pos[j] <- pos[j] - 1
        s <- s + N
      } else break
    }
    p <- p - s
  }
  #last delimiter:
  pos[nd] <- pos[nd] - p
  pos
}

- RoelandV