我目前正在python中使用itertools.combinations((函数，并希望使用生成的组合访问特定组合的索引。这里有一个例子：
使用此代码生成索引及其相应组合：
it = itertools.combinations(range(6),2)
for i in enumerate(it):
print(i)
结果：
(0, (0, 1, 2, 3))
(1, (0, 1, 2, 4))
(2, (0, 1, 2, 5))
(3, (0, 1, 3, 4))
(4, (0, 1, 3, 5))
(5, (0, 1, 4, 5))
(6, (0, 2, 3, 4))
(7, (0, 2, 3, 5))
(8, (0, 2, 4, 5))
(9, (0, 3, 4, 5))
(10, (1, 2, 3, 4))
(11, (1, 2, 3, 5))
(12, (1, 2, 4, 5))
(13, (1, 3, 4, 5))
(14, (2, 3, 4, 5))
我希望能够使用排序的元组(0，3，4，5(来有效地映射到索引9。有没有一个闭形式的函数，我可以推广来实现这一点？我最初尝试了一个多索引，但当推广到一个大的组合对象时，这是不切实际的缓慢。
作为确定这样一个函数的潜在起点，在思考这个问题的同时，我意识到每个第一个数字(d1(出现的次数可以表示为(n-(d1+1(选择p-1(。在这个例子中，n＝6，p＝4，所以有(5选择3(或10次0，4选择3或4次1，依此类推。我无法确定一种简单的方法来将其推广到重复值的d2-4，或者将其转换为索引。
这可以通过动态编程来解决。假设您的组合长度为p，结构为：(c_0, c_1, c_2, ..., c_{p-1})。首先计算小于(c_0, c_0+1, c_0+2, ..., c_0+p-1)的迭代次数。之后，将数组缩减为(c_1, c_2, ..., c_{p-1})-c_0-1。然后做同样的事情，直到数组的长度为1。
from math import comb
import numpy as np
import itertools
def find_niterations_before_c0(max_val, p, c0):
'''
Suppose combination_i = (c_0, c_1, c_2, ..., c_{p-1})
This function will return the number of combinations before
(c_0, c_0+1, c_0+2, ..., c_{p-1}+p-1)
'''
n = max_val
k = max_val-p+1
return sum([comb(n-i,k-i) for i in range(c0)])
def get_index(combination_i, stop):
# This function finds the position of the given combination using DP
# Suppose range <stop> = 6 and combination_i = (1,2,3,5)
# 1. Calculate number of iterations before (1,2,3,4) which is 10
# 2. Reduce combination to (0,1,3) and new <stop> = 4
# 3. Calculate number of iterations before (0,1,2) which is 0
# 4. Reduce combination to (0,2) and new <stop> = 3
# 5. Calculate number of iterations before (0, 1) which is 0
# 6. Reduce combinations to (1,) and new <stop> = 2
# 7. Calculate number of iterations before (1, ) which is 1
# 8. Array length is 1. Return total iterations.
combination_i = np.array(combination_i)
ret = 0
while(True):
p = len(combination_i)
ret += find_niterations_before_c0(stop-1, p, combination_i[0])
stop = stop - 1 - combination_i[0]
combination_i = combination_i[1:] - 1 - combination_i[0]
if p == 1:
return ret
下面是一个运行示例：
stop = 6
p = 4
it = itertools.combinations(range(stop), p)
for combination_i in it:
ind = get_index(combination_i, stop)
print(ind, combination_i)
[Output]:
0 (0, 1, 2, 3)
1 (0, 1, 2, 4)
2 (0, 1, 2, 5)
3 (0, 1, 3, 4)
4 (0, 1, 3, 5)
5 (0, 1, 4, 5)
6 (0, 2, 3, 4)
7 (0, 2, 3, 5)
8 (0, 2, 4, 5)
9 (0, 3, 4, 5)
10 (1, 2, 3, 4)
11 (1, 2, 3, 5)
12 (1, 2, 4, 5)
13 (1, 3, 4, 5)
14 (2, 3, 4, 5)
你也可以计算出非常大的数字。
get_index((6, 10, 12, 13, 16, 50), 60)
[Output]:
25005038