有序列表的可逆组合生成器

Question

我有代码，其中给出了一个有序整数列表，我生成了几个新列表，我需要能够将这些列表与从 1 到 N 的整数一对一映射，选择 k（或 0 到（ N在python).

中选择k)-1)

例如，如果我有一个 N=7，k=3，那么我可能会从列表 [0,1,2] 开始，我可能会用 0 枚举它。然后我生成列表 [0,1 ,3]、[0,1,5] 和 [3,4,6] 都需要由 0,...,34.

范围内的整数唯一标识

我知道我可以使用 itertools 生成有序列表，

itertools.combinations(range(7), 3)

但我需要一个反函数，它比简单地搜索预生成的列表更有效，因为我将使用大 N 并且每个列表引用大约 50 个新列表。

Answer 1

您可以使用 itertools 食谱中的这个食谱 here:

def nth_combination(iterable, r, index):
    'Equivalent to list(combinations(iterable, r))[index]'
    pool = tuple(iterable)
    n = len(pool)
    if r < 0 or r > n:
        raise ValueError
    c = 1
    k = min(r, n-r)
    for i in range(1, k+1):
        c = c * (n - k + i) // i
    if index < 0:
        index += c
    if index < 0 or index >= c:
        raise IndexError
    result = []
    while r:
        c, n, r = c*r//n, n-1, r-1
        while index >= c:
            index -= c
            c, n = c*(n-r)//n, n-1
        result.append(pool[-1-n])
    return tuple(result)

用法示例：

>>> nth_combination(range(7), 3, 5)
(0, 2, 3)
>>> nth_combination(range(7), 3, 34)
(4, 5, 6)

反转：

from math import factorial
def get_comb_index(comb, n):
    k = len(comb)
    rv = 0
    curr_item = 0
    n -= 1
    for offset, item in enumerate(comb, 1):
        while curr_item < item:
            rv += factorial(n-curr_item)//factorial(k-offset)//factorial(n+offset-curr_item-k)
            curr_item += 1
        curr_item += 1
    return rv

用法示例：

>>> get_comb_index((4,5,6), 7)
34
>>> get_comb_index((0,1,2), 7)
0
>>> get_comb_index((0,2,4), 7)
6

有序列表的可逆组合生成器

Invertible combination generator for ordered lists

python

list

generator

inverse

combinatorics