Алгоритм для python itertools.permutations

Ответ 1

Вам нужно понять математическую теорию циклов перестановки также известную как "орбит" (важно знать оба "условия искусства" поскольку математический объект, сердце combinatorics, довольно продвинутый, и вам может потребоваться найти исследовательские статьи, которые могут использовать один или оба термина).

Для более простого введения в теорию перестановок wikipedia может помочь. Каждый из указанных мной URL-адресов предлагает разумную библиографию, если вы получаете достаточно увлеченные комбинаторикой, чтобы захотеть исследовать ее дальше и получить реальное понимание (я лично сделал это для меня как хобби;).

Как только вы поймете математическую теорию, код все еще тонкий и интересный для "обратной инженерии". Ясно, что indices - это просто текущая перестановка в терминах индексов в пул, учитывая, что получаемые элементы всегда задаются

yield tuple(pool[i] for i in indices[:r])

Таким образом, сердце этого увлекательного механизма cycles, которое представляет собой орбиты перестановок и вызывает indices, чтобы быть обновленным, в основном с помощью утверждений

j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]

Т.е. если cycles[i] равно j, это означает, что следующим обновлением индексов является замена i-го (слева) на j-й один справа (например, если j равно 1, то последний элемент indices заменяется - indices[-1]). И тогда там менее частое "массовое обновление", когда элемент cycles достигло 0 во время его декрементов:

indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i

это ставит i -ный элемент indices в самом конце, сдвигая все следующие элементы индексов один влево и указывает, что в следующий раз, когда мы перейдем к этому элементу cycles, мы будем заменяя новый i -й элемент indices (слева) на n - i th (справа) - это будет i th снова, за исключением, конечно, того факта, что там будет

cycles[i] -= 1

прежде чем мы рассмотрим его; -).

Трудная часть, конечно, будет доказать, что это работает, т.е. что все перестановки исчерпывающе сгенерированы без перекрытия и корректного "синхронизированного" выхода. Я считаю, что вместо доказательства может быть проще посмотреть, как работает механизм, когда он полностью раскрывается в простых случаях - комментируя утверждения yield и добавляя print ones (Python 2. *), мы имеем

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    print 'I', 0, cycles, indices
    # yield tuple(pool[i] for i in indices[:r])
    print indices[:r]
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
        print 'B', i, cycles, indices
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
        print 'A', i, cycles, indices
            else:
        print 'b', i, cycles, indices
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
        print 'a', i, cycles, indices
                # yield tuple(pool[i] for i in indices[:r])
            print indices[:r]
                break
        else:
            return

permutations('ABC', 2)

Выполнение этого показывает:

I 0 [3, 2] [0, 1, 2]
[0, 1]
b 1 [3, 1] [0, 1, 2]
a 1 [3, 1] [0, 2, 1]
[0, 2]
B 1 [3, 0] [0, 2, 1]
A 1 [3, 2] [0, 1, 2]
b 0 [2, 2] [0, 1, 2]
a 0 [2, 2] [1, 0, 2]
[1, 0]
b 1 [2, 1] [1, 0, 2]
a 1 [2, 1] [1, 2, 0]
[1, 2]
B 1 [2, 0] [1, 2, 0]
A 1 [2, 2] [1, 0, 2]
b 0 [1, 2] [1, 0, 2]
a 0 [1, 2] [2, 0, 1]
[2, 0]
b 1 [1, 1] [2, 0, 1]
a 1 [1, 1] [2, 1, 0]
[2, 1]
B 1 [1, 0] [2, 1, 0]
A 1 [1, 2] [2, 0, 1]
B 0 [0, 2] [2, 0, 1]
A 0 [3, 2] [0, 1, 2]

Сосредоточьтесь на cycles: они начинаются с 3, 2 - затем последний уменьшается, поэтому 3, 1 - последнее не равно нулю, поэтому у нас есть "небольшое" событие (один своп в индексы) и разбить внутренний цикл. Затем мы вводим его снова, на этот раз декремент последнего дает 3, 0 - последнее теперь равно нулю, поэтому это "большое" событие - "массовая свопинг" по индексам (ну, здесь не так много массы, но, может быть;-), а циклы вернутся к 3, 2. Но теперь мы не прервали цикл for, поэтому продолжим, уменьшая следующий (последний) первый (последний) - который дает незначительное событие, один своп индексов, и мы снова разбиваем внутренний цикл. Вернемся к циклу, но опять же последний уменьшился, на этот раз давая 2, 1 - второстепенное событие и т.д. В конце концов цикл целых для цикла встречается только с крупными событиями, без второстепенных - когда циклы начинаются как все, поэтому декремент принимает каждый к нулю (главное событие), no yield происходит в этом последнем цикле.

Так как no break когда-либо выполнялся в этом цикле, мы берем ветвь else for, которая возвращает. Обратите внимание, что while n может немного вводить в заблуждение: он фактически действует как while True - n никогда не изменяется, цикл while выходит только из этого оператора return; его можно было бы также выразить как if not n: return, за которым следует while True:, потому что, конечно, если n есть 0 (пустой пул), то ничего не получится после первого тривиального пустого yield. Автор просто решил сохранить пару строк, свернув проверку if not n: с помощью while; -).

Я предлагаю вам продолжить изучение еще нескольких конкретных случаев - в конечном итоге вы должны понимать, что работает "часовой механизм". Сначала сосредоточьтесь только на cycles (возможно, отредактируйте инструкции print соответственно, удалив из них indices), так как их ход по часовой стрелке по их орбите является ключом к этому тонкому и глубокому алгоритму; как только вы это почувствуете, способ indices получить должным образом обновленный ответ на последовательность cycles почти антиклима!!)