发电机功能内的逻辑帮助

Question

我试图创建一个生成器函数：

def combinations(iterable, r, maxGapSize):
    maxGapSizePlusOne = maxGapSize+1

    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))

    while True:
        for i in reversed(range(r)):        
            if indices[i] != i + n - r:     
                break
        else:
            return

        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1

        previous = indices[0]
        for k in indices[1:]:
            if k-previous>maxGapSizePlusOne:
                isGapTooBig = True
                break
            previous = k
        else:
            isGapTooBig = False

        if not isGapTooBig:
            print(indices)


combinations(("Aa","Bbb","Ccccc","Dd","E","Ffff",),2,1)

我正在打印出我希望用于从名为“iterable”的参数中选择元素的索引，以便进行调试。这给了我：

[0, 2]
[1, 2]
[1, 3]
[2, 3]
[2, 4]
[3, 4]
[3, 5]
[4, 5]

忽略[0,1]，因为这是在其他地方产生的。。。你知道吗

这正是我想要的，但我猜我的代码过于复杂和低效。iterable的大小可能有几千个，也可能是maxGapSize < 5。你知道吗

有什么建议可以帮我做得更好吗？你知道吗

Answer 1

您的大部分代码看起来与Python code for itertools.combination完全相同。itertools.combination的CPython实现是用C编写的。你知道吗

只需使用itertools.combination而不是使用与Python等效的代码，就可以加快函数的速度：

import itertools as it
def mycombinations(iterable, r, maxGapSize):
    maxGapSizePlusOne = maxGapSize+1    
    for indices in it.combinations(range(len(iterable)),r):
        previous = indices[0]
        for k in indices[1:]:
            if k-previous>maxGapSizePlusOne:                    
                break
            previous = k
        else:
            yield indices   
            # print(indices)

您可以使用timeit以这种方式比较替代实现的相对速度：

原始版本：

% python -mtimeit -s'import test' 'list(test.combinations(("Aa","Bbb","Ccccc","Dd","E","Ffff",),2,1))'
10000 loops, best of 3: 63.9 usec per loop

与

使用itertools.combination:

% python -mtimeit -s'import test' 'list(test.mycombinations(("Aa","Bbb","Ccccc","Dd","E","Ffff",),2,1))'
100000 loops, best of 3: 17.2 usec per loop

---

上面的代码生成所有组合，包括初始组合range(len(iterable))。我觉得这样更漂亮。但是如果你真的想删除第一个组合，你可以使用

def mycombinations(iterable, r, maxGapSize):
    ...
    comb=it.combinations(range(len(iterable)),r)
    next(comb)
    for indices in comb:

---

顺便说一下，函数combinations实际上并不依赖于iterable。它只取决于iterable的长度。因此，最好是打电话签名

def combinations(length, r, maxGapSize):