python - 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 个 block ，我们能否找到这些 block 中的第 n 个组合，但不会生成所有组合。或者换句话说，如果位置可以被 x 整除。

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

编辑/添加:此问题的推理是针对列表为 range(0,1000000) 且 r =30000 的情况。然后提供一个组合，求它是否能被 x 整除。自然地，实际的索引会非常大(而且生成的完整组合太多了)

Answer 1

看看Combinatorial number system维基百科文章。

这是我在 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)