生成格式良好的嵌套堆栈推送和弹出操作

Question

我正在开发一个使用简单堆栈的项目，并在所述堆栈上进行操作。

操作包括：

NoOp    # Do nothing, leave stack as-is
Push(i) # Push value i onto stack
Pop(i)  # Pop top value of stack, raise if popped value != i or stack is empty

我有一个函数接受这些指令的序列，并从空堆栈开始按顺序执行它们。然后返回最终堆栈。在我的例子中，returns 一个空堆栈被认为是良构的序列。

格式正确的序列示例：

() # The empty sequence
NoOp
Push(x), Pop(x)
Push(x), NoOp, NoOp, NoOp, Pop(x), NoOp # NoOps are OK sprinkled anywhere
Push(x), Push(y), Pop(y), Pop(x) # Nesting is OK

不是格式正确的序列的例子：

Push(x) # Does not leave an empty stack
Pop(x) # Attempt to pop from empty stack
Push(x), Push(y), Pop(x), Pop(y) # Improper nesting, Pop(x) will get y and error

出于测试目的，我希望能够为给定的最大长度 N 生成所有格式正确的指令序列。有没有一种方法可以使用 itertools 完成此操作而不生成 all 序列排列并过滤掉无效序列？

Answer 1

好的，所以我们可以通过递归来做到这一点。

基本情况是没有元素。

如果我们查看可能的模式，我们会发现所有情况都以 NoOps 或 Push 开头。

NoOps -> 后跟 N-1 的序列
推。 Push 的不同之处在于它必须跟在 pop 之后。但是你注意到你可以注意到唯一的序列是 push(x) - 一些序列 - pop(x) - 一些序列。请注意，某些序列可能为空或可能包含 N-2 个元素

从这些想法中，我们可以得出以下算法。

x = 0


def combinations(N):
    global x
    result = []     # A list of all the combinations of length N

    # Base case
    if N == 0:
        return [""]

    # Cases with NoOps followed by some sequence
    last_part=combinations(N-1)
    for i in last_part:
        result.append("NoOp, " + i)

    # Cases with Push(x) - some sequence - Pop(x) - some sequence
    if N > 1:
        for i in range(1, N):
            part1 = combinations(i-1)
            part2 = combinations(N-i-1)
            for j in part1:
                for k in part2:
                    result.append("Push(" + str(x) + "), " + j + "Pop("+ str(x) + "), " + k)
                    x += 1
    return result

# This is just to test. Change N to whatever it needs to be.
result = combinations(4)
for line in result:
    print(line)

对于 N=4 它将 return:

NoOp, NoOp, NoOp, NoOp,
NoOp，NoOp，推送 (0)，弹出 (0)，
NoOp, Push(1), Pop(1), NoOp,
NoOp, Push(2), NoOp, Pop(2),
推送(4)，弹出(4)，NoOp，NoOp，
推送(5)，弹出(5)，推送(3)，弹出(3)，
推送(6)，NoOp，弹出(6)，NoOp，
推送 (8)，NoOp，NoOp，弹出 (8)，
推送(9), 推送(7), 弹出(7), 弹出(9),

编辑 - 从 0...N

获取所有结果

我认为有人试图发表的评论是，您可能不仅想要 N returned 的结果，还想要 0...N 的结果。添加此行：

result += combinations(N-1)

在 return 语句之前。对于 N == 2 它将 return:

NoOp, NoOp,
无操作，
推送(0)，弹出(0)，
无操作，
"""

Answer 2

所以，感谢 Stef 的回答，我能够构建一个完美运行的生成器方法。

def yield_sum_splits(n: int) -> typ.Iterable[typ.Tuple[int, int]]:
    """Given an integer, returns all possible sum splits.
    For any given split (a, b), a + b will always equal n.

    For example:
        5   -> (0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)
        -5  -> (0, -5), (-1, -4), (-2, -3), (-3, -2), (-4, -1), (-5, 0)
    """
    sign = int(math.copysign(1, n))
    an = abs(n)
    for i in range(an + 1):
        yield (sign * i, sign * (an - i))


def yield_valid_stack_cmd_seqs(length: int) -> typ.Iterable[str]:
    """Lazily yields valid stack command sequences.

    Valid stack command sequences are properly nested and balanced.
    """
    counter = itertools.count(start=0)

    def helper(n: int) -> typ.Iterable[str]:
        if n <= 0:
            # Exactly one sequence of length 0.
            yield ()
            return

        # Generate sequences of NoOp + Subcombinations(n - 1).
        subcombinations = helper(n - 1)
        for subcombination in subcombinations:
            yield ('NoOp', *subcombination)

        # Generate sequences of the form:
        #     Push(x) + Subcombinations(a) + Pop(x) + Subcombinations(b),
        # where a >= 0, b >= 0, and a + b = (length - 2).
        if n >= 2:
            for a, b in yield_sum_splits(n - 2):
                a_sub = helper(a)
                b_sub = helper(b)

                # Use itertools.product when using yield.
                # Nested for loops would omit some outputs, strangely.
                for a_part, b_part in itertools.product(a_sub, b_sub):
                    i = next(counter)
                    pu_op = f'Push({i})'
                    po_op = f'Pop({i})'
                    yield (pu_op, *a_part, po_op, *b_part)

    yield from helper(length)

生成格式良好的嵌套堆栈推送和弹出操作

Generating well-formed nested stack push and pop operations

python

combinatorics