Комбинация в Python

Question

Я пытаюсь понять алгоритм комбинаций в Python

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 используется в этой функции, какова их роль.
Пожалуйста, помогите мне.

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 когда мы вернемся к рекурсивному вызову.

Теперь это решение имеет экспоненциальную сложность по времени, так как это решение методом грубой силы.

Надеюсь, это поможет!