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种组合的情况它们都能正常运行，但是在更多的组合情况下表现不佳。

编辑：有人写了类似的内容然后删除了它，那个帖子几乎是完美的...

alphaNumList = list(DATA_ALPHA_NUM)
alphaNumList.insert(0, "")

result = ["".join(item) for item in 
itertools.islice(itertools.product(alphaNumList, repeat=6), 0,1)]

- Switch

---

@Jean-FrançoisFabre 我知道，但我想不用循环来完成。我需要非常快地获取索引.. - Switch

有人写了这样的代码："result = ["".join(item) for item in itertools.islice(itertools.product(alphaNumList, repeat=6), 0,1)]"，它几乎完美，但停止得太早了。 - Switch

是的，但这个想法在这里。 - Switch

谢谢！希望他能再次帮助我！ - Switch

最后你朋友的回答并没有帮到我。因为问题出现在8192左右，我们回到了“a”，而不是“aaa”，但我通过设置来删除重复项来解决了它！无论如何，非常感谢你们两个！ - Switch

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()函数的更快版本。

其中一种方法是预先计算阶乘，然后在需要时查找它们：

fact = [1]
for i in range(1, 1000):
    fact.append(fact[-1] * i)

def comb(n, r):
    return fact[n] // (fact[r] * fact[n - r])

还有一种避免使用大阶乘并且不需要辅助存储的方法：

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]

这意味着当你对长度为8的字符串'ABCDEFGH'进行itertools.combinations('ABCDEFGH', 3)组合运算时，每次取出r=3个字母，会有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

- Raymond Hettinger

---

哦，好的，谢谢。我之前用阶乘写过类似的东西。我明白你的意思，我想。 - Switch

工作正常，但需要太长的时间:/ - Switch

Answer 2

您不想要组合。确实，您想要“aa”。但是使用组合，因为您从不选择两个相同的项目，所以不会发生这种情况。

因此，这里有一个适当的版本，使用“累积乘积”，确实，就像Raymond使用组合一样，我必须计算（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"

更新：我已添加了一种方法来检索在两个索引之间的列表，基于相同的概念，但在这种情况下，切片更好地使用 :)

def getCombiListBetween(fromNumber, toNumber):
    combiList = []
    if fromNumber < toNumber:
        pF, pT = 0, 0
        while cumulative[pF] < fromNumber:
            pF += 1
        while cumulative[pT] < toNumber:
            pT += 1
        start = fromNumber - 1 - (cumulative[pF - 1] if pF > 0 else 0)
        end = toNumber - 1
        for p in range(pF, pT + 1):
            combiList += ["".join(item) for item in itertools.islice(itertools.product(alphaNumList, repeat=p + 1), start, min(cumulative[p], end) + 1)]
            start = 0
            end -= cumulative[p]
    else:
        combiList.append(getCombiFromIndex(fromNumber))
    return combiList

print(getCombiListBetween(8189, 8191)) # ['][', ']]', 'aaa']

- Vince