生成所有排列：为什么递归中的产生值不在输出中？

Question

我在 CS61A 中遇到了问题：

给定一个唯一元素的序列，该序列的排列是一个以某种任意顺序包含序列元素的列表。例如，
[2, 1, 3]
、
[1, 3, 2]
和
[3, 2, 1]
是序列
1, 2, 3]
的一些排列。

实现
gen_perms
，一个生成器函数，它接受序列
seq
并返回一个生成
seq
的所有排列的生成器。对于此问题，假设
seq
不会为空。

可以按任何顺序产生排列。

我的解决方案是：

def gen_perms(seq):
    def generator(seq_):
        list_seq=list(seq_)
        if len(list_seq)==1:
            yield list_seq
        else:
            for item in generator(list_seq[1:]):
                for i in range(len(list_seq)):
                    yield item[:i]+[list_seq[0]]+item[i:]
    return generator(seq)

调用示例：

print(list(gene_perms([1, 2, 3])))

上面的代码输出了预期的结果：

[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

我的疑问是它看起来不应该有正确的输出。在我的代码中，

generator

是递归构建的，

yield

的

generator(list_seq[1:])

行出现在

generator(list_seq)

之前，它应该首先产生其子序列的排列，然后才产生序列本身的排列。但前者甚至没有出现在输出中。

有人可以向我解释一下吗？也许我对发电机的工作原理有错误的理解。

Answer 1

尽管更深层次的递归调用的

yield

发生得更早，但这些产生的值会被进行更深层次递归调用的 for 循环所消耗

。这些产生的值不会神奇地冒出整个递归树！它们由直接调用者使用，而不是由递归堆栈更高层的任何调用者使用。

每个生成器执行（唯一）负责向其直接消费者产生值。递归中更深层次的调用不会产生顶级调用者将看到的值。

关于您的代码的其他备注

与你的问题无关，但是：

如果您的代码得到一个空列表作为输入，它将进入无限递归。为了避免这种情况，请将其作为递归的基本情况。
您应该在代码中显式产生
lists，而不是通过执行 list(seq_)
```
 或执行 
```
[seq[0]]
```
，因为：
```
- yield
```
 中也取一个切片来注入第一个元素，所以不是 
```
  [seq[0]]
```
 （创建列表），而是 
```
  seq[:1]
```
：这也适用于字符串和元组。
```
- 切片）
- 突变任何生成的排列。此外，如果顶级调用者如此不明智地改变他们从此进程中获得的列表，则不会对该进程产生负面影响。原因是您在循环中执行的 yield
```
 已经创建了一个新序列（通过使用切片和 
```
  +
```
 运算符）。
```
由于您的内部函数与外部函数具有相同的签名（参数和返回类型），因此您不需要内部函数：只需递归调用
gen_perms
```
 即可。
```

考虑到这些点，你的函数可以是：

def gen_perms(seq):
    if not seq:
        yield seq
    else:
        for item in gen_perms(seq[1:]):
            for i in range(len(seq)):
                yield item[:i] + seq[:1] + item[i:]

运行示例

print(*gen_perms([1,2,3]))  # list input
# -> [1, 2, 3] [2, 1, 3] [2, 3, 1] [1, 3, 2] [3, 1, 2] [3, 2, 1]
print(*gen_perms((1,2,3)))  # tuple input
# -> (1, 2, 3) (2, 1, 3) (2, 3, 1) (1, 3, 2) (3, 1, 2) (3, 2, 1)
print(*gen_perms("abc"))    # string input
# -> abc bac bca acb cab cba

（诚然，输入不应该是

range

 实例，因为输出不能具有“排列”范围；不存在这样的事情。我假设代码挑战并不打算使用范围对象调用此函数）

生成所有排列：为什么递归中的产生值不在输出中？

问题描述投票：0回答：1

1个回答

最新问题

生成所有排列：为什么递归中的产生值不在输出中？

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1