生成格式良好的嵌套堆栈push和pop操作

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

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

形成良好的序列示例：

() # 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来实现这一点，而不必生成所有序列排列并过滤掉无效的序列？你知道吗

Answer 1

所以，多亏了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)

Answer 2

好的，我们可以通过递归来实现。你知道吗

基本情况是如果没有元素。你知道吗

如果我们看看可能的模式，我们可以看到，所有的情况下，要么开始与NoOps或推。你知道吗

1. NoOps—>；后跟N-1的顺序
2. 推。Push的不同之处在于它后面必须跟一个pop。但是你注意到你可以注意到唯一的序列是push（x）-some sequence-pop（x）-some sequence。请注意，某些序列可能为空，或者可能有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，它将返回：

• NoOp，NoOp，NoOp，NoOp，

• NoOp，NoOp，按（0），弹出（0），

• NoOp，按（1），弹出（1），NoOp，

• NoOp，Push（2），NoOp，Pop（2），

• 按（4），弹出（4），NoOp，NoOp，

• 按（5），弹出（5），按（3），弹出（3），

• 按（6），NoOp，Pop（6），NoOp，

• 按（8），NoOp，NoOp，Pop（8），

• 按（9），按（7），弹出（7），弹出（9），

编辑-用于获取0…N的所有结果

我想有人想说的是，您可能不仅希望返回N的结果，还希望返回0…N的结果。添加以下行：

result += combinations(N-1)

在return语句之前。对于N==2，它将返回：

• NoOp，NoOp，

• 不，

• 按（0），弹出（0），

• 不，

• “”