如何用Python生成器实现DFS排列的逐值返回？

要实现每次调用get_value()返回一个排列结果，你需要将原有的DFS排列函数改造成生成器（Generator），并在类中维护生成器的状态，每次调用时获取下一个值。以下是两种实现方式：

方式一：手动改造DFS为生成器 #

将原有的递归排列函数修改为生成器，用yield替代列表append，避免一次性生成所有排列：

class Solution:
    def __init__(self, lst):
        # 初始化时创建排列生成器实例
        self.perm_generator = self._dfs_permutation(lst)
    
    def _dfs_permutation(self, lst):
        # 递归生成器版本的排列函数
        if len(lst) == 0:
            yield []
            return
        if len(lst) == 1:
            yield lst
            return
        
        for i in range(len(lst)):
            current = lst[i]
            remaining = lst[:i] + lst[i+1:]
            # 递归遍历剩余元素的排列，拼接当前元素后yield
            for perm in self._dfs_permutation(remaining):
                yield [current] + perm
    
    def get_value(self):
        try:
            # 获取生成器的下一个排列
            return next(self.perm_generator)
        except StopIteration:
            # 所有排列已生成完毕，返回None（可根据需求调整）
            return None

if __name__=='__main__':
    s = Solution(['1','2','3','4'])
    v1 = s.get_value()  # 输出: ['1', '2', '3', '4']
    print(v1)
    v2 = s.get_value()  # 输出: ['1', '2', '4', '3']
    print(v2)
    # 继续获取剩余排列
    while True:
        val = s.get_value()
        if val is None:
            break
        print(val)

关键改动说明： #

• 将原permutation函数改为私有生成器_dfs_permutation，用yield逐个返回排列，而非一次性存入列表。
• 在类的__init__方法中初始化生成器，维护其状态。
• get_value通过next()调用生成器，获取下一个排列；当生成器耗尽时捕获StopIteration异常，返回None。

方式二：使用Python内置itertools.permutations #

如果不需要手动实现DFS逻辑，Python标准库的itertools.permutations提供了高效的排列生成器，代码更简洁：

import itertools

class Solution:
    def __init__(self, lst):
        # 将permutations的结果转换为列表（原返回元组）
        self.perm_generator = (list(p) for p in itertools.permutations(lst))
    
    def get_value(self):
        try:
            return next(self.perm_generator)
        except StopIteration:
            return None

if __name__=='__main__':
    s = Solution(['1','2','3','4'])
    print(s.get_value())  # ['1', '2', '3', '4']
    print(s.get_value())  # ['1', '2', '4', '3']

优势： #

• itertools是Python内置的高效实现，性能优于手动编写的DFS，尤其适合处理大列表。
• 代码量更少，无需维护递归逻辑。

内容的提问来源于stack exchange，提问作者pylos