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

Question

Может кто-нибудь объяснить, пожалуйста, алгоритм для itertools.permutations рутины в стандартном Python lib 2.6? Я не понимаю, почему это работает.

Код:

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)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Answer 1

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

Для более простого введения в теорию перестановок может помочь 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 -й (справа) - это снова будет 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]

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

Поскольку 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 почти антилимакс! -)

Answer 2

Проще ответить с шаблоном результатов, чем словами (за исключением того, что вы хотите знать математическую часть теории), так что распечатки - лучший способ объяснить.
Самое тонкое, что после завершения цикла он сам переустанавливается на первый ход последнего раунда и начинает следующий цикл вниз или постоянно сбрасывается до первого хода последнего, даже большего раунда, как часы.

Часть кода, выполняющая задание сброса:

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

целом:

In [54]: 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)
    ...:     yield tuple(pool[i] for i in indices[:r])
    ...:     print(indices, cycles)
    ...:     while n:
    ...:         for i in reversed(range(r)):
    ...:             cycles[i] -= 1
    ...:             if cycles[i] == 0:
    ...:                 indices[i:] = indices[i+1:] + indices[i:i+1]
    ...:                 cycles[i] = n - i
    ...:                 print("reset------------------")
    ...:                 print(indices, cycles)
    ...:                 print("------------------")
    ...:             else:
    ...:                 j = cycles[i]
    ...:                 indices[i], indices[-j] = indices[-j], indices[i]
    ...:                 print(indices, cycles, i, n-j)
    ...:                 yield tuple(pool[i] for i in indices[:r])
    ...:                 break
    ...:         else:
    ...:             return

часть результата:

In [54]: list(','.join(i) for i in permutations('ABCDE', 3))
([0, 1, 2, 3, 4], [5, 4, 3])
([0, 1, 3, 2, 4], [5, 4, 2], 2, 3)
([0, 1, 4, 2, 3], [5, 4, 1], 2, 4)
reset------------------
([0, 1, 2, 3, 4], [5, 4, 3])
------------------
([0, 2, 1, 3, 4], [5, 3, 3], 1, 2)
([0, 2, 3, 1, 4], [5, 3, 2], 2, 3)
([0, 2, 4, 1, 3], [5, 3, 1], 2, 4)
reset------------------
([0, 2, 1, 3, 4], [5, 3, 3])
------------------
([0, 3, 1, 2, 4], [5, 2, 3], 1, 3)
([0, 3, 2, 1, 4], [5, 2, 2], 2, 3)
([0, 3, 4, 1, 2], [5, 2, 1], 2, 4)
reset------------------
([0, 3, 1, 2, 4], [5, 2, 3])
------------------
([0, 4, 1, 2, 3], [5, 1, 3], 1, 4)
([0, 4, 2, 1, 3], [5, 1, 2], 2, 3)
([0, 4, 3, 1, 2], [5, 1, 1], 2, 4)
reset------------------
([0, 4, 1, 2, 3], [5, 1, 3])
------------------
reset------------------(bigger reset)
([0, 1, 2, 3, 4], [5, 4, 3])
------------------
([1, 0, 2, 3, 4], [4, 4, 3], 0, 1)
([1, 0, 3, 2, 4], [4, 4, 2], 2, 3)
([1, 0, 4, 2, 3], [4, 4, 1], 2, 4)
reset------------------
([1, 0, 2, 3, 4], [4, 4, 3])
------------------
([1, 2, 0, 3, 4], [4, 3, 3], 1, 2)
([1, 2, 3, 0, 4], [4, 3, 2], 2, 3)
([1, 2, 4, 0, 3], [4, 3, 1], 2, 4)