计算组合的等级？

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

会magic是什么？

最初我想将它存储为尺寸为13 x 13 x 13的3维矩阵,因此我可以轻松地将其编入索引.虽然这对于13选择3来说是好的,但对于像13选择7这样的东西来说这会有太多的开销.

我不想使用dict,因为最终这个代码将在C中,无论如何数组都会更高效.

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

更新:为了说清楚,我正在努力节省空间.这些组合中的每一个实际上都指向占用大量空间的东西,比方说2千字节.如果我使用13x13x13阵列,那将是4兆字节,其中我只需要572千字节使用(13选3)点.

Answer 1

这是一个概念性答案和基于lex排序如何工作的代码.(所以我猜我的答案就像"白痴"的答案,除了我认为他的细节太少而且他的链接太多了.)我unchoose(n,S)为你编写了一个函数,假设S是一个有序列表子集range(n).想法:S包含0或不包含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,而不是递减和使用尾递归.

Answer 2

您可以尝试使用组合的词典索引.也许这个页面会有所帮助:http://saliu.com/bbs/messages/348.html

这个MSDN页面有更多细节:生成数学组合的第m个词典元素.

更具体一点:

当被视为元组时,您可以按字典顺序排列组合.

所以(0,1,2)<(0,1,3)<(0,1,4)等

假设您有0到n-1的数字,并从中选择了k.

现在,如果第一个元素为零,则您知道它是第一个n-1中的一个选择k-1.

如果第一个元素是1,那么它是下一个n-2中的一个选择k-1.

这样,您可以递归计算给定组合在词典排序中的确切位置,并使用它将其映射到您的数字.

这也是相反的,MSDN页面解释了如何做到这一点.