algorithm - 计算组合的等级？

Question

我想为一组组合中的每个组合预先计算一些值。例如，当从 0 到 12 中选择 3 个数字时，我将为每个数字计算一些值:

>>> for n in choose(range(13), 3):
    print n, foo(n)

(0, 1, 2) 78
(0, 1, 3) 4
(0, 1, 4) 64
(0, 1, 5) 33
(0, 1, 6) 20
(0, 1, 7) 64
(0, 1, 8) 13
(0, 1, 9) 24
(0, 1, 10) 85
(0, 1, 11) 13
etc...

我想将这些值存储在一个数组中，以便给定组合，我可以计算它并获取值。例如:

>>> a = [78, 4, 64, 33]
>>> a[magic((0,1,2))]
78

魔法会是什么？

最初我想将它存储为大小为 13 x 13 x 13 的 3 维矩阵，这样我就可以轻松地以这种方式对其进行索引。虽然这对于 13 选 3 没问题，但对于 13 选 7 之类的东西来说，这会产生太多开销。

我不想使用字典，因为最终这段代码将使用 C 语言，而数组无论如何都会更有效率。

更新:我也有类似的问题，但使用重复组合，所以任何关于如何获得这些排名的答案将不胜感激=)。

更新:为了清楚起见，我试图节省空间。这些组合中的每一个实际上索引到占用大量空间的东西，比方说 2 KB。如果我要使用 13x13x13 阵列，那将是 4 兆字节，其中我只需要 572 千字节使用(13 选择 3)点。

Answer 1

这是一个概念性的答案和一个基于 lex 排序如何工作的代码。 (所以我想我的回答就像“白痴”一样，除了我认为他的细节太少而他的链接太多。)我写了一个函数 unchoose(n,S)假设 S 是 range(n) 的有序列表子集，这对您有效.想法:要么 S 包含 0，要么不包含。如果是，则删除 0 并计算剩余子集的索引。如果没有，则它位于 binomial(n-1,k-1) 之后。确实包含 0 的子集。

def binomial(n,k):
    if n < 0 or k < 0 or k > n: return 0
    b = 1
    for i in xrange(k): b = b*(n-i)/(i+1)
    return b

def unchoose(n,S):
    k = len(S)
    if k == 0 or k == n: return 0
    j = S[0]
    if k == 1: return j
    S = [x-1 for x in S]
    if not j: return unchoose(n-1,S[1:])
    return binomial(n-1,k-1)+unchoose(n-1,S)

def choose(X,k):
    n = len(X)
    if k < 0 or k > n: return []
    if not k: return [[]]
    if k == n: return [X]
    return [X[:1] + S for S in choose(X[1:],k-1)] + choose(X[1:],k)

(n,k) = (13,3)
for S in choose(range(n),k): print unchoose(n,S),S

现在，您也可以缓存或哈希这两个函数的值，二项式和非选择。这样做的好处在于，您可以在预先计算所有内容和不预先计算任何内容之间做出折衷。例如，您可以仅针对 len(S) <= 3 进行预计算.

您还可以优化 unchoose，使其在 S[0] > 0 循环中添加二项式系数。 ，而不是递减和使用尾递归。