Python中的组合

Question

我试图理解python中的组合函数Algo

def combinations(iterable, r):   
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    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
        yield tuple(pool[i] for i in indices)    

但我无法理解为什么if indices[i] != i + n - r:和

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

is在这个功能中使用了它们的作用。 请帮我 。

Answer 1

我认为像这样的解决方案会做，你想要实现的目标

combinationDict = []

def combinations(iterable, r, cnt, subPart):
  if cnt > r:
    return
  if cnt == r:
    combinationDict.append(subPart)
    return
  if (len(iterable) < r):
    return  
  i = 0
  while i < len(iterable):
    combinations(iterable[:i]+iterable[i+1:], r, cnt+1, subPart+iterable[i])
    combinations(iterable[:i]+iterable[i+1:], r, cnt, subPart)
    i += 1

combinations("ABCD", 2, 0, "")
print(combinationDict)

基本上上述解决方案的主要目的是，在递归的每个步骤，要么在i处添加特定元素，要么不将其添加到组合中。

让我们说例如ABCD和2，我们从A开始，然后我们添加B，然后我们看到大小是2，我们返回，我们将C添加到A，因为我们返回到递归调用。

现在，解决方案具有指数时间复杂度，因为它是一种强力解决方案。

希望这可以帮助！