I'm trying to solve the following exercise from "Data Structures and Algorithms in Python" by Goodrich et al.:

"Describe a nonrecursive algorithm for enumerating all permutations of the numbers {1, 2, ..., n} using an explicit stack."

The hint for this excercise is to use "[...] a stack to reduce the problem to that of enumerating all permutations of the numbers {1, 2, ..., n-1}."

My first idea was to push n onto the stack, then n - 1, ..., until I reach 1. Now, I'd save all permutations of 1 ("1") in a list. The next step would be to pop the next value from the stack ("2") and to insert it into every possible position for every permutation that is in my list so far. As a result, when the stack is empty again, there would be a list containing all permutations of the numbers 1 to n.

However, I doubt that this is what is meant by the hint (I'm using an extra list, which is not mentioned in the hint, for example). What other approaches are there that fit the hint better?

Edit: This is my implementation of the solution I've described

def permutations(n):
    s = MyStack()
    perms = [[]]
    while n > 0:
        s.push(n)
        n -= 1
    
    total = 1
    factor = 1

    while not s.is_empty():
        val = s.pop()

        total *= factor
        factor  = 1

        prev = perms
        perms = [None] * total
        idx = 0

        for perm in prev:
            for pos in range(len(perm)   1):
                perms[idx] = [*perm[:pos], val, *perm[pos:]]
                idx  = 1

    for perm in perms:
        print(perm)

Edit 2: explicit stack implementation of @btilly‘s answer

def permutations_explicit_stack(items):
    items = list(items)
    n = len(items)
    s = MyStack()
    i = 0
    perm = []
    
    while i < n:
        perm.append(items.pop(0))
        s.push(i)
        i = 0
        
        if len(items) == 0:
            print(perm)
            
            while i == len(items) and s:
                i = s.pop()
                items.append(perm.pop())
                i  = 1

CodePudding user response：

Better hint. Write a recursive function to calculate permutations. That uses an implicit stack. Then figure out how to use an explicit stack to do the same thing that the recursive function did, but without having to use recursion. The point of the exercise being to understand what your programming language did for you with recursion.

The reason why this matters is that, as you learn data structures, you'll encounter more and more situations where recursion really is easier. But you'll also encounter situations where rewriting it with an explicit stack allows you to understand and modify the algorithm in a way that straight recursion hid from you. A classic example being that depth first search is easiest to write recursively. But if you rewrite with a stack, then switch the stack for a queue, you get breadth first search. And switch out the queue for a priority queue, and you've got A* search.

Here is a recursive permutation function to get you started.

def permutations (items):
    _permutations([], list(items))

def _permutations(perm, items):
    if 0 == len(items):
        print(perm)
    else:
        for i in range(len(items)):
            perm.append(items.pop(0))
            _permutations(perm, items)
            items.append(perm.pop())

What information is being kept on the implicit function call stack? And how can you store the same information in an explicit stack? How can you rewrite this function without any recursion?