Рекурсивное понимание списка для перестановки. Python

Question

У меня есть функция в python, которая запрограммирована рекурсивной в понимании списка. Но я не понимаю, что на самом деле происходит в нем!

def permut(s,l): 
    if l == []: return [[s]] 
    return [ e + [l[0]] for e in permut(s, l[1:])] + [l+[s]] 

Функция получает два аргумента, во-первых строку, а второй список и возвращает перестановку строки в списке.

permut('a', [1,2,3]) 
[['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']] 

Может кто-нибудь объяснить, что происходит в понимании списка?

Answer 1

Если синтаксис списка понимание бросает тебя, вы можете переписать эту функцию следующим образом и добавить некоторую отладочную print() S по пути:

def permut(s,l): 
    print("Entering function permut()") 
    print("Parameters:\ns: {}\nl: {}".format(s,l)) 
    if l == []: 
     print("End of recursion reached, returning {}".format([[s]])) 
     return [[s]] 
    result = [] 
    for e in permut(s, l[1:]): 
     result.append(e + [l[0]]) 
    result += [l + [s]] 
    print("Returning {}".format(result)) 
    return result 

Это выход вы получите:

>>> permut('a', [1,2,3]) 
Entering function permut() 
Parameters: 
s: a 
l: [1, 2, 3] 
Entering function permut() 
Parameters: 
s: a 
l: [2, 3] 
Entering function permut() 
Parameters: 
s: a 
l: [3] 
Entering function permut() 
Parameters: 
s: a 
l: [] 
End of recursion reached, returning [['a']] 
Returning [['a', 3], [3, 'a']] 
Returning [['a', 3, 2], [3, 'a', 2], [2, 3, 'a']] 
Returning [['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']] 
[['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']] 

Answer 2

Прежде всего, у вас есть a вместо s в рекурсии permut звонок.

return [ e + [l[0]] for e in permut(a, l[1:])] + [l+[s]] 

Во-первых, он вычисляет permut(s, l[1:]), то есть: пытается переставлять s и часть списка без первого элемента. Он выталкивает первый элемент, пока он есть, тогда рекурсивный вызов возвращает [[s]].

Теперь, идя назад в вызовах, s будет «добавлена» к каждому элементу рекурсивно созданного списка, то данный l добавляется, а результаты:

# l == [] 
return [['a']] 

# e == ['a'] 
# l == [3], l[0] == 3 
return [['a'] + [3]] + [[3] + [a]] 
# equals [['a', 3], [3, 'a']] 

# e == ['a', 3] then [3, 'a'] 
# l == [2, 3], l[0] == 2 
return [['a', 3] + [2], [3, 'a'] + [2]] + \ 
     [[2, 3] + [a]] 
# equals [['a', 3, 2], [3, 'a', 2], [2, 3, 'a']] 

# e == ['a', 3, 2] then [3, 'a', 2] then [2, 3, 'a'] 
# l == [1, 2, 3], l[0] == 1 
return [['a', 3, 2] + [1], [3, 'a', 2] + [1], [2, 3, 'a'] + [1]] + \ 
     [[1, 2, 3] + ['a']] 
# equals [['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']] 

Может быть, это не красиво читать, но это своего рода работы. Вы можете видеть, что e извлекается как единственный элемент списка, возвращенного на предыдущем уровне.

Вы также можете попробовать:

def tee(parm): 
    print parm 
    return parm 

И переопределять permut как:

def permut(s,l): 
    if l == []: return [[s]] 
    return [ e + [l[0]] for e in tee(permut(s, l[1:]))] + [l+[s]] 

Мой вывод:

[['a']] 
[['a', 3], [3, 'a']] 
[['a', 3, 2], [3, 'a', 2], [2, 3, 'a']] 
[['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']] 

который охватывает рекурсивные вызовы.