Itertools 组合查找组合是否可整除

Question

给定 r 为 4 的 itertools 组合：

from itertools import combinations

mylist = range(0,35) 
r = 4
combinationslist = list(combinations(mylist, r))

这将输出：

(0, 1, 2, 3)
(0, 1, 2, 4)
(0, 1, 2, 5)
(0, 1, 2, 6)
(0, 1, 2, 7)
(0, 1, 2, 8)
(0, 1, 2, 9)
...
(30, 31, 32, 33)
(30, 31, 32, 34)
(30, 31, 33, 34)
(30, 32, 33, 34)
(31, 32, 33, 34)

我的问题是，如果我们将列表分成 10 个块，我们能否找到这些块中的第 n 个组合，但不生成所有组合。或者换句话说，如果该位置可以被 x 整除。

问题之一是头寸将达到数十亿，并且可能无法推导出 n 是多少。是否有一种启发式方法可以确定特定的元素组合/序列是否可以被 x 整除

编辑/添加：这个问题的推理是针对列表为 range(0,1000000) 且 r =30000 的情况。然后提供一个组合，判断它是否能被x整除。当然，实际的索引将非常巨大（并且完整的组合太多而无法生成）

Answer 1

查看组合数系统维基百科文章。

这是我在 Python 中想到的：

from math import comb

def combo_index(combo, n):
    result = 0
    i = 0
    for j, item in enumerate(combo):
        k = len(combo) - j
        result += comb(n - i, k)
        result -= comb(n - item, k)
        i += item - i + 1
    return result

使用您的示例进行演示，其中n=35：

>>> len(combinationslist)
52360
>>> combo = random.choice(combinationslist)
>>> combo
(15, 17, 23, 28)
>>> combinationslist[combo_index(combo, 35)]
(15, 17, 23, 28)

这是一种递归方法

def combo_index_r(combo, n):
    k = len(combo)
    if k == 0 or k == n:
        return 0
    if k == 1:
        return combo[0]
    combo = tuple(x - 1 for x in combo)
    if combo[0] == -1:
        return combo_index_r(combo[1:], n - 1)
    return comb(n - 1, k - 1) + combo_index_r(combo, n - 1)