有没有更好的算法来为组合分配数字？

Question

众所周知，帕斯卡恒等式可以用于将从n个元素中选择k个组合编码为一个数字，该数字在0到(n \choose k) - 1范围内（我们称这个数字为组合索引），使用组合数系统。假设算术操作的时间恒定，此算法需要O(n)的时间。^† 我有一个应用程序，其中k ≪ n，并且O(n)时间的算法是不可行的。是否有一种算法可以将0到(n \choose k) - 1之间的数字双向分配给n个元素中选择k个组合，其运行时间为O(k)或类似时间复杂度？该算法不需要计算与组合数系统相同的映射，但是反向计算需要在类似的时间复杂度内可计算。

---

† 具体来说，从组合索引计算组合的算法需要 O(n) 的时间。如果您预先计算二项式系数，则从组合计算组合索引的时间为 O(k)。

- fuz

---

你必须将它映射到0和(n \choose k) - 1之间的“密集”范围内的数字吗？如果您可以将其放宽到更稀疏的范围，那么很容易想出一些w(n)的东西。 - Ami Tavory

@AmiTavory 地图对于我的目的必须是密集的。 - fuz

预处理怎么样？如果可以，时间/空间限制是什么？ - Ami Tavory

@j_random_hacker 确实。说得好。我没有考虑到这一点。 - fuz

@AmiTavory 嗯，你可以使用预先计算好的系数查找表。 - fuz

Answer 1

评论的描述。

对于给定的组合指数 (N)，要找到第 k 位数字，需要找到 c_k，使得 (c_k \choose k) <= N 且 ((c_k+1) \choose k) > N。

设 P(i,k) = i!/(i-k)!。

P(i, k) = i * (i-1) * ... * (i-k+1)
substitute x = i - (k-1)/2
  = (x+(k-1)/2) * (x+(k-1)/2-1) * ... * (x-(k-1)/2+1) * (x-(k-1)/2)
  = (x^2 - ((k-1)/2)^2) * (x^2 - ((k-1)/2-1)^2) * ...
  = x^k - sum(((k-2i-1)/2)^2))*x^(k-2) + O(x^(k-4))
  = x^k - O(x^(k-2))
P(i, k) = (i - (k-1)/2)^k - O(i^(k-2))

从上述不等式中：

(c_k \choose k) <= N
P(c_k, k) <= N * k!
c_k ~= (N * k!)^(1/k) + (k-1)/2

我不确定O(c_k^(k-2))部分有多大。我想它不会对结果产生太大影响。如果它的数量级是(c_k+1)/(c_k-k+1)，那么近似结果非常好。原因如下：

((c_k+1) \choose k) = (c_k \choose k) * (c_k + 1) / (c_k - k + 1)

我会尝试类似以下的算法：

For given k
Precalculate k!

For given N
For i in (k, ..., 0)
  Calculate c_i with (N * i!)^(1/i) + (i-1)/2
  (*) Check is P(c_i, k) <=> N * i!
    If smaller check c_i+1
    If larger check c_i-1
    Repeat (*) until found P(c_i, i) <= N * i! < P(c_i+1, i)
  N = N - P(c_i, i)

如果近似值很好，步骤数远小于k，则找到一个数字的时间复杂度为O(k)。

- Ante