алгоритм для Python itertools.permutations

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

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

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

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

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

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

Т.е., если циклы [i] равно j , это означает, что следующее обновление индексов - заменить i-е (слева) на j-е справа (например, если j равно 1, то последний элемент индексов заменяется местами - индексы [-1] ). Кроме того, существует менее частое «массовое обновление», когда элемент циклов достиг 0 во время его декрементов:

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

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

cycles[i] -= 1

, прежде чем мы его изучим в следующий раз ;-).

Самой сложной частью, конечно же, было бы доказать , что это работает - то есть, что все перестановки генерируются исчерпывающе, без перекрытия и правильно «синхронизированного» выхода.Я думаю, что вместо доказательства может быть проще посмотреть, как механизм работает при полном раскрытии в простых случаях - комментируя утверждения yield и добавляя print операторов ( 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]

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

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

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