递归列表推导用于排列组合。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']]

有人能解释一下列表推导式中发生了什么吗？

- Oni1

---

递归调用中的“from”是什么意思？ - kaspersky

是的，你说得对，Tim P。 - Oni1

你真正想做什么？这是你自己的代码吗？如果不是，你是想修复其中的错误还是只是想理解它？ - Karl Knechtel

我想了解列表推导式中到底发生了什么？ - Oni1

Answer 1

如果列表推导式的语法让您感到困惑，您可以按照以下方式重写此函数，并在其中添加一些调试 print() 语句：

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']]

- Tim Pietzcker

---

不是的，什么情况下变量e总是有值？ - Oni1

@T.C. 它遍历了 permut(s, l[1:]) 的返回值，意味着它首先是 ['a', 3, 2, 1]，然后是 [3, 'a', 2, 1]，...（使用你在问题中提供的示例）。 - Verena Haunschmid

Answer 2

首先，在递归的permut调用中，你使用了a而不是s。

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']]

这段内容涉及递归调用。

- TNW

---

为了计算permut('a', [1, 2, 3])，需要先计算permut('a', [2, 3])。其中，调用了permut('a', [3])，它又调用了permut('a', [])。这样，permut('a', []) 是第一个调用并具备返回值所需的所有内容，因此它将返回值返回给更高层级，进而能够计算返回值 - 如此循环，向前调用，向后返回结果。然而，可以使用“尾递归”来避免向后跳转 - 我鼓励您探索这个主题（虽然这与 Python 不太相关）。 - TNW