Python获取组合的索引

Question

例如，我需要生成从“a”到“]]]]]]”的组合，为了实现这个目的，我使用了这个python脚本。在

import itertools

DATA_ALPHA_NUM = 
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789&-
()@=+;/!%$\\'\",.<>*^{}#~_[]"
b = 10

for i in range(1,int(b)+1):
   for e in itertools.combinations(DATA_ALPHA_NUM,i): print(''.join(e))

但现在我需要做相反的事情，例如：如果我给新脚本“1”，它将输出“a”，如果我给90，它将输出“]”等。

我写了几个脚本，在不到737191的组合中工作得很好，但之后就不好了。在

编辑：有人写了这样的东西，然后在几乎完美的情况下删除它。。在

^{pr2}$

Answer 1

概述

关键是遍历累积组合，直到达到索引为止。在

解决方案

from math import factorial

def comb(n, r):
    'Combinations of n things taken r at a time'
    return factorial(n) // (factorial(r) * factorial(n - r))

def nth_combination(population, r, index):
    'Equivalent to list(combinations(population, r))[index]'
    n = len(population)
    c = comb(n, r)
    if index < 0:
        index += c
    if index < 0 or index >= c:
        raise IndexError
    if r < 0 or r > n:
        raise ValueError
    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(population[-1-n])
    return tuple(result)

优化

如果需要考虑速度，则可以构建更快版本的comb（）函数。在

一种方法是预先计算阶乘，然后在需要时进行查找：

^{pr2}$

还有另一种方法可以完全避免大阶乘，而且不需要辅助存储：

def comb(n, r):
    c = 1
    r = min(r, n-r)
    for i in range(1, r+1):
        c = c * (n - r + i) // i
    return c

工作原理

首先将组合分解为其组成组：

def groups(n, r):
    return [comb(n-i-1, r-1) for i in range(n-r+1)]

>>> comb(8, 3)
56
>>> groups(8, 3)
[21, 15, 10, 6, 3, 1]

这意味着，当您一次运行itertools.combinations('ABCDEFGH', 3)处理n=8个字母时，有56个组合。前21个以A开头，后15个以B开头，下10个以C开头，下6个以D开头，下3个以E开头，最后1个以F开头。在

假设你想找到56个组合中的第25个。它属于第二组，所以你的第一个字母是B。在

由于25-21是4，那么您需要在itertools.combinations('CDEFGH', 2)定义的“B”组的15个成员中找到第4个组合。重复上述过程，直到所有的字母都被提取出来。在

测试

下面是一个测试，以确保它能产生预期的结果：

from itertools import combinations

population = 'ABCDEFGH'
for r in range(len(population) + 1):
    for i, expected in enumerate(combinations(population, r)):
        actual = locate(list(population), r, i)
        assert expected == actual

Answer 2

你不想要组合。的确，你想要“aa”。但对于组合，因为你永远不会选择两次相同的项目，这是不会发生的。在

所以这里有一个“累积积”的正确版本，实际上，就像雷蒙德对组合所做的那样，我必须数数（90，90+90**2，90+90**2+90**3，…）来找出与我所跟踪的组合对应的好的幂。在

请注意，它并没有优化，因为我在分割产品。。。只值一个！在

import itertools

alphaNumList = list("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789&-()@=+;/!%$\\'\",.<>*^{}#~_[]")

cumulative = [len(alphaNumList)]
for i in range(1, 10):
    cumulative.append(len(alphaNumList) ** (i+1) + cumulative[i - 1])


def getCombiFromIndex(combiNumber):
    p = 0
    while cumulative[p] < combiNumber:
        p += 1  # WARNING : not robust to combi greater than (10,90) in my case :)
    rest = combiNumber - 1 - (cumulative[p - 1] if p > 0 else 0)
    return "".join([item for item in itertools.islice(itertools.product(alphaNumList, repeat=p + 1), rest, rest + 1)][0])


print(getCombiFromIndex(1))  # "a"
print(getCombiFromIndex(90))  # "]"
print(getCombiFromIndex(91))  # "aa"
print(getCombiFromIndex(800064))  # "ah+1"

更新：我添加了一个方法来检索两个索引之间的列表，基于相同的概念，但在本例中，最好使用slice:）

^{pr2}$