Может ли кто-нибудь объяснить этот код перестановки Python?

Question

Я видел некоторые публикации кода для перестановок здесь, но я не смог найти хороший пошаговый обзор того, что на самом деле происходит. Если бы кто-то мог просто объяснить, что на самом деле происходит на каждом этапе этого кода, я был бы очень признателен. Кажется, я не могу обернуться вокруг этого. Код, на который я смотрю, написан на Python и http://snippets.dzone.com/posts/show/753.

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]


for p in all_perms(['a','b','c']):
    print p

Answer 1

def all_perms(str):
    # If there is only one item, there can be only one permutation
    # yield the single item
    if len(str) <=1:
        yield str
    else:
        # loop over the permutations returned by a recursive call to all_perms
        # note it is passing a subset of the list passed in.
        for perm in all_perms(str[1:]):
            # for each returned sub-permutation insert the item that
            # wasn't passed into each possible position.
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]


for p in all_perms(['a','b','c']):
    print p

Итак, вы переходите в ['a','b','c'].

Он вызывает all_perms(['b', 'c']), и это вызывает all_perms(['c']), что приводит к 'c'.

оператор yield означает, что all_perms() является генератором тот факт, что он вызывает сам себя, означает, что он использует рекурсию .

Я бы рекомендовал использовать itertools.permutations вместо этого фрагмента.

Answer 2

Прежде всего, имя параметра str - неправильный выбор. Вероятно, это связано с тем, что он работает для всех типов последовательностей в Phyton, но это должно быть seq или что-то еще, чтобы прояснить намерение.

1. Если длина списка <= 1 (пустой или один элемент), вернуть список (для этого случая есть только одно решение). </p>

2. Для всех остальных случаев:

   a) Создайте все перестановки str[1:] (то есть список только без элемента head).

   b) Вставьте элемент head в каждой позиции каждой перестановки, созданной в a), и верните результат

yield работает немного как return; Основное отличие состоит в том, что текущее значение возвращается и, когда функция вызывается снова, оно продолжается с инструкцией после yield.

Таким образом, результат легко собрать.

Пример:

'a' дает 'a' (тривиально). 'ab' сначала отбивает голову ('a'), затем создает все перестановки b (есть только одна: 'b' сама). Теперь головка вставляется в каждую позицию, поэтому мы получаем 'ab' (заголовок + список) и 'ba' (список + заголовок).

и т.д.

Answer 3

То, что вы видите, это генератор итераторов . Это функция, которая возвращает объект, который можно зациклить.

во время выполнения цикла for, all_perms выполняется до точки, где он достигает yield. Значение yield ed передается в цикл как переменная p. Затем выполнение all_perms продолжается в позиции после оператора yield, где метод завершился в прошлый раз.