Начинающий Python смущен сложной строкой кода

Question

Я понимаю суть кода, что он образует перестановки; однако мне было интересно, может ли кто-нибудь объяснить точно, что происходит в операторе возврата.

def perm(l):
    sz = len(l)
    print (l)
    if sz <= 1:
        print ('sz <= 1')
        return [l]
    return [p[:i]+[l[0]]+p[i:] for i in range(sz) for p in perm(l[1:])]

Answer 1

Это return возвращает понимание списка, элементы которого создаются путем вставки первого элемента l в каждую позицию p, от первого до последнего - p, в свою очередь, представляет собой список списки, полученные рекурсивным вызовом perm, который исключает первый элемент l (и, таким образом, переставляет все другие элементы всеми возможными способами).

Если вы не понимаете рекурсию, объяснять это не тривиально ;-). Если вы не понимаете понимания списка, они являются тривиальными для объяснения - что return семантически эквивалентно

result = []
for i in range(sz):
  for p in perm(l[1:]):
    result.append(p[:i]+[l[0]]+p[i:])
return result

это также показывает, насколько неэффективен этот код: он вызывает perm рекурсивно sz раз, и, очевидно, в этом нет необходимости. Намного лучше было бы просто поменять местами две for петли:

result = []
for p in perm(l[1:]):
  for i in range(sz):
    result.append(p[:i]+[l[0]]+p[i:])
return result

и эквивалент этого, намного лучшего кода, представляет собой понимание списка с заменой двух for предложений:

return [p[:i]+[l[0]]+p[i:] for p in perm(l[1:]) for i in range(sz)]

Answer 2

В операторе возврата используется понимание списка. Это немного легче понять, если поместить его в реальные циклы:

value = []
for i in range(sz):
    # call this function using all but the first item in l
    for p in perm(l[1:]):
        # now place the first item in l between index i-1 and index i in p
        value.append(p[:i] + [l[0]] + p[i:])
return value

Answer 3

Хорошо, начнем.

Стартовый код

(без выписок)

def perm(l):
    sz = len(l)
    if sz <= 1:
        return [l]
    return [p[:i]+[l[0]]+p[i:] for i in range(sz) for p in perm(l[1:])]

Редакция 1

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]
    return [p[:i] + [s[0]] + p[i:]
            for i in range(len(s)) for p in perm(s[1:])]

• Переименовать l в s
• Удалите sz, вместо этого используйте len(s) напрямую. Мы можем чуть-чуть потерять эффективность, но мы получим огромное количество читабельности
• Исправить пробел в понимании списка

Редакция 2

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # A list of permutations
    permutations = []
    for i in range(len(s)):
        # Recursively find all permutations of s[1:]
        for p in perm(s[1:]):
            # Insert s[0] in position i
            permutations.append(p[:i] + [s[0]] + p[i:])
    return permutations

• Разбейте понимание списка

Редакция 3

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # A list of permutations
    permutations = []
    # Recursively find all permutations of s[1:]
    for p in perm(s[1:]):
        for i in range(len(s)):
            # Insert s[0] in position i
            permutations.append(p[:i] + [s[0]] + p[i:])
    return permutations

• Изменить вложенность циклов for. Теперь вы можете сказать: для каждой перестановки, занять каждую позицию i и добавить копию этой перестановки с s[0], вставленной в каждую позицию i. Это станет яснее в следующих нескольких ревизиях.

Редакция 4

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # Recursively find all permutations of s[1:]
    shortperms = perm(s[1:])
    # A list of permutations
    permutations = []
    for shortperm in shortperms:
        for i in range(len(s)):
            # Make a copy of shortperm
            spcopy = shortperm[:]
            # Insert s[0] in position i
            spcopy.insert(s[0], i)
            # Add this to the list of permutations
            permutations.append(spcopy)
    return permutations

• Перемещен вызов функции perm. Теперь переменная shortperms будет содержать все перестановки s[1:], что составляет s минус первый элемент.
• Изменено добавление списка в три операции:
  • Сделайте копию shortperm
  • Вставьте первый элемент в s
  • Добавить этот список к permutations

Редакция 5

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # Recursively find all permutations of s[1:]
    shortperms = perm(s[1:])
    # A list of permutations
    permutations = []
    for shortperm in shortperms:
        for i in range(len(shortperm) + 1):
            # Make a copy of shortperm
            spcopy = shortperm[:]
            # Insert s[0] in position i
            spcopy.insert(s[0], i)
            # Add this to the list of permutations
            permutations.append(spcopy)
    return permutations

• len(s) - это то же самое, что и len(shortperm) + 1, потому что каждый shortperm - это перестановка элементов в s, за вычетом первого. Однако, это, вероятно, более читабельно.

Финальный код

С комментарием к документации

def perm(s):
    """Return a list of all permutations of the items in the input
    sequence."""
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # Recursively find all permutations of s[1:]
    shortperms = perm(s[1:])
    # A list of permutations
    permutations = []
    for shortperm in shortperms:
        for i in range(len(shortperm) + 1):
            # Make a copy of shortperm
            spcopy = shortperm[:]
            # Insert s[0] in position i
            spcopy.insert(s[0], i)
            # Add this to the list of permutations
            permutations.append(spcopy)
    return permutations

Answer 4

Посмотрите на это:

>>> l = [1, 2, 3, 4, 5, 6]
>>> p = l[1:]
>>> p
[2, 3, 4, 5, 6]
>>> i = 3
>>> p[:i]
[2, 3, 4]
>>> p[i:]
[5, 6]
>>> p[:i]+[l[0]]+p[i:]
[2, 3, 4, 1, 5, 6]
>>> 

Итак, вот в чем дело, p обозначает все перестановки l[1:] (то есть l минус первый элемент). Далее, i равно range(sz), что означает, что оно варьируется от 0 до длины l. Это разделит p на два списка всех возможных размеров (0 и sz, 1 и sz -1, 2 и sz - 2 и т. Д.) И вставит первый элемент l - тот, который не был переставлен - между этими двумя списками.

Answer 5

В документации Python для itertools.permutations() функции есть пара примеров, которые легче переварить. Обратите внимание, что эта функция является новой в Python 2.6, поэтому она не будет доступна для вас, если вы используете что-то более старое.

Есть также много примеров и объяснений в SO беседах, которые уже произошли в недалеком прошлом, которые также представляют хорошее чтение:

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

Как создать все перестановки списка в Python