计算组合的排名？ [英] Compute rank of a combination?

问题描述

欲$ P $对 - 计算一些值在一组的组合的每个组合。例如，选择从0 3数字时至12日，我将计算为每一个有一定价值：

I want to pre-compute some values for each combination in a set of combinations. For example, when choosing 3 numbers from 0 to 12, I'll compute some value for each one:

>>> 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...

我要存储在数组中这些值，以便给定的结合，我可以计算其和得到的值。例如：

I want to store these values in an array so that given the combination, I can compute its and get the value. For example:

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

会是什么魔术是？

起初我以为只是其存储为尺寸13×13×13的3-D矩阵，这样我就可以很容易地建立索引的方式。虽然这是罚款13选3，这将有太多的开销，像13选7。

Initially I thought to just store it as a 3-d matrix of size 13 x 13 x 13, so I can easily index it that way. While this is fine for 13 choose 3, this would have way too much overhead for something like 13 choose 7.

我不希望使用的字典，因为这最终code将在C和数组会更有效呢。

I don't want to use a dict because eventually this code will be in C, and an array would be much more efficient anyway.

更新：我也有类似的问题，但使用的组合有重复，所以如何获得这些军衔任何答案将是非常美联社preciated =）

UPDATE: I also have a similar problem, but using combinations with repetitions, so any answers on how to get the rank of those would be much appreciated =).

更新：为了明确这一点，我试图以节省空间。每个组合的实际索引到的东西占用了大量的空间，比方说2千字节。如果我用一个13x13x13阵列，这将是4兆，而我只需要使用572千字节（13选3）点。

UPDATE: To make it clear, I'm trying to conserve space. Each of these combinations actually indexes into something take up a lot of space, let's say 2 kilobytes. If I were to use a 13x13x13 array, that would be 4 megabytes, of which I only need 572 kilobytes using (13 choose 3) spots.

推荐答案

下面是一个概念性的答案和code根据排序法是如何工作。 （所以我想我的答案是这样的白痴的，但我认为他有过一些细节和他联系有太多的。）我写了一个函数 unchoose（N，S）为你的作品假设S是范围（N）的有序列表子集。这个想法：要么S包含0或没有。如果确实如此，除去0和计算指数为剩余的子集。如果没有的话，就来后的二项式（N-1，K-1）那些包含0的子集。

Here is a conceptual answer and a code based on how lex ordering works. (So I guess my answer is like that of "moron", except that I think that he has too few details and his links have too many.) I wrote a function unchoose(n,S) for you that works assuming that S is an ordered list subset of range(n). The idea: Either S contains 0 or it does not. If it does, remove 0 and compute the index for the remaining subset. If it does not, then it comes after the binomial(n-1,k-1) subsets that do contain 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

现在，这也是事实，你可以缓存或两种功能，二项分布和unchoose的哈希值。什么是好的关于这个，你可以precomputing一切，precomputing之间什么都没有妥协。例如，您可以precompute只为 LEN（S）LT; = 3

Now, it is also true that you can cache or hash values of both functions, binomial and unchoose. And what's nice about this is that you can compromise between precomputing everything and precomputing nothing. For instance you can precompute only for len(S) <= 3.

您还可以优化unchoose，使其增加了二项式系数与循环，如果 S [0]＆GT; 0 ，而不是递减，并使用尾递归。

You can also optimize unchoose so that it adds the binomial coefficients with a loop if S[0] > 0, instead of decrementing and using tail recursion.

这篇关于计算组合的排名？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！