我想为一组组合中的每个组合预先计算一些值。例如，当从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是什么？
magic
最初，我认为只是将其存储为大小为13 x 13 x 13的3-d矩阵，因此我可以轻松地对其进行索引。虽然这对于13选择3来说很好，但是对于13选择7这样的东西会产生太多开销。
我不想使用dict，因为最终此代码将在C中使用，并且无论如何数组都将更加高效。
更新：我也有一个类似的问题，但是结合使用重复和重复，因此任何关于如何获得那些排名的答案都将受到赞赏=）。
更新：为了清楚起见，我正在尝试节省空间。这些组合中的每一个实际上都索引到占用大量空间的东西上，比如说2 KB。如果我要使用13x13x13阵列，那将是4兆字节，其中我只需要572 KB的（13个选择3个）点即可。
这是一个概念性的答案，以及基于词法排序原理的代码。（因此，我想我的答案类似于“白痴”，只是我认为他的细节太少，链接的内容也太多。）我unchoose(n,S)为您编写了一个函数，假定S是的有序列表子集range(n)。这个想法：S要么包含0，要么不包含0。如果是这样，请删除0并计算其余子集的索引。如果不是，则在binomial(n-1,k-1)确实包含0 的子集之后。
unchoose(n,S)
range(n)
binomial(n-1,k-1)
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。
len(S) <= 3
您还可以优化取消选择，以使其在if的情况下通过循环添加二项式系数S[0] > 0，而不是递减并使用尾递归。
S[0] > 0
