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

Question

众所周知，Pascal 恒等式可用于将 n 中的 k 元素组合编码为从 0 到 (n\choose k) - 1(我们称这个数字为组合索引)使用combinatorial number system .假设算术运算的时间恒定，则此算法需要 O(n) 时间。^†

我有一个应用程序，其中 k ≪ n 并且 O(n) 时间内的算法是不可行的。是否有一种算法可以将 0 和 (n\choose k) - 1 之间的数字双射分配给 n 中的 k 个元素的组合谁的运行时间是 O(k) 或类似的？该算法不需要计算与组合数系统相同的映射，但是，需要以相似的时间复杂度计算逆。

---

† 更具体地说，根据组合索引计算组合的算法运行时间为 O(n)。如果您预先计算二项式系数，则可以在 O(k) 时间内从组合中计算出组合指数。

Answer 1

评论的描述。

对于给定的组合索引 ( N )，找到 k'th需要找到的数字 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)

如果近似值很好，number of steps << k , 而不是找到一个数字是 O(k)。