引导排列生成的递归错误

Question

我目前正试图找出如何绕过 Python 排列的递归限制，该排列遵守一些规则以减少排列总数。现在，我正在使用的简化版本可确保前一个符号与最后一个符号不同：

def recursive_generate_sequences(symbols_dict, sequence=None, last_symbol=None, start_symbols=None, remaining=0):
    """
    Generate all possible sequences of symbols based on their counts.

    :param start_symbols: set of symbols that are the known beginning of the sequence
    :param symbols_dict: dictionary containing the symbol and the number of times it appears in the sequence
    :param sequence: reserved for recursive function, do not pass
    :param last_symbol:  reserved for the recursive function last symbol the function pushed out
    :param remaining: reserved for the recursive function, do not pass
    :return:
    """
    if sequence is None:
        sequence = []
        counts = {symbol: count for symbol, count in symbols_dict.items()}
        # Initialize the remaining count, so that we don't have to recalculate it all the time
        remaining = sum(counts.values())
        # Initialize the sequence with the start symbols if provided
        if start_symbols:
            for symbol in start_symbols:
                if symbol in counts and counts[symbol] > 0:
                    sequence.append(symbol)
                    counts[symbol] -= 1
                    remaining -= 1
                    last_symbol = symbol
                else:
                    raise ValueError(f"Start symbol '{symbol}' is not valid or has insufficient count.")
    else:
        counts = symbols_dict

    # check if the sequence is complete
    if remaining == 0:
        yield sequence

    for symbol, count in counts.items():
        if count > 0 and symbol != last_symbol:
            # explore the rabbit hole
            counts[symbol] -= 1
            next_sequence = sequence + [symbol]
            # pass None to start_symbols for recursive calls
            yield from recursive_generate_sequences(counts, next_sequence, symbol, None, remaining - 1)
            counts[symbol] += 1  # Backtrack

if __name__ == "__main__":
    # works
    for x in recursive_generate_sequences({'a': 1, 'b': 2, 'c': 1}):
        print(x)

    # fails with RecursionError
    for x in recursive_generate_sequences({'a': 1000, 'b': 2000, 'c': 1000}):
        pass

但是正如你可能会告诉我的那样，当symbols_dict值高于python的递归限制时，我就达到了递归限制。

我看过堆栈溢出和一个MCoding视频答案建议采用迭代方法，另一个堆栈溢出答案建议将其包装在另一个函数中。

我无法真正理解迭代方法，并且我无法让第二个建议在他们提供的简单代码之外正常工作。在理想的世界中，答案采用生成器的形式，该生成器按其调用方式生成，并且不会尝试提前计算所有内容。

任何人都可以帮我将其切换为迭代方法或更好地解释第二个堆栈溢出答案吗？

Answer 1

好吧，我还有事要做！！我最终明白了 mCoding 的含义，所以我创建了这个类来处理排列生成器：

class IterativeGenerateSequences:
    def __init__(self, symbols_dict: Dict, start_symbols: Optional[List] = None):
        self.symbols_dict = symbols_dict
        self.start_symbols = start_symbols
        self.counts = {symbol: count for symbol, count in symbols_dict.items()}
        self.stack = []
        self._initialize_stack()

    def _initialize_stack(self):
        # initialize starting state based on start_symbols if provided
        initial_sequence = []
        initial_counts = self.counts.copy()
        remaining = sum(initial_counts.values())

        if self.start_symbols:
            for symbol in self.start_symbols:
                if symbol in initial_counts and initial_counts[symbol] > 0:
                    initial_sequence.append(symbol)
                    initial_counts[symbol] -= 1
                    remaining -= 1
                else:
                    raise ValueError(f"Start symbol '{symbol}' is not valid or has insufficient count.")

        # initial state includes the sequence so far, the counts of remaining symbols, and the last symbol added...
        self.stack.append((initial_sequence, initial_counts, None, remaining))

    def generate(self):
        while self.stack:
            sequence, counts, last_symbol, remaining = self.stack.pop()

            # sequence is complete, yield it
            if remaining == 0:
                yield sequence
                continue

            for symbol, count in counts.items():
                if count > 0 and symbol != last_symbol:
                    # prep the next state to explore
                    next_counts = counts.copy()
                    next_counts[symbol] -= 1
                    next_sequence = sequence + [symbol]
                    next_remaining = remaining - 1

                    # push the new state onto the stack
                    self.stack.append((next_sequence, next_counts, symbol, next_remaining))

要注意的关键是我从递归方法切换到迭代方法。绝对可以随意批评/优化，因为我是迭代器与递归的新手。