我想在一组组合中为每个组合预先计算一些值.例如,当从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)点.
我知道有一种算法允许,在给定数字组合(无重复,无顺序)的情况下,计算字典顺序的索引.
对我的应用来说,加速事情会非常有用......
例如:
combination(10, 5)
1 - 1 2 3 4 5
2 - 1 2 3 4 6
3 - 1 2 3 4 7
....
251 - 5 7 8 9 10
252 - 6 7 8 9 10
我需要算法返回给定组合的索引.
es:index( 2, 5, 7, 8, 10 )- > index
编辑:实际上我正在使用一个生成所有组合C(53,5)的Java应用程序并将它们插入到TreeMap中.我的想法是创建一个包含我可以使用此算法索引的所有组合(和相关数据)的数组.
一切都是加速组合搜索.但是我尝试了一些(不是全部)解决方案,你提出的算法比TreeMap中的get()慢.
如果它有帮助:我的需求是从0到52的5到53的组合.
再次感谢大家:-)