Python Non-recursive Permutation

Question

Does anyone understand the following iterative algorithm for producing all permutations of a list of numbers?

I do not understand the logic within the while len(stack) loop. Can someone please explain how it works?

# Non-Recursion
@param nums: A list of Integers.
@return: A list of permutations.

def permute(self, nums):
    if nums is None:
        return []
    nums = sorted(nums)
    permutation = []
    stack = [-1]
    permutations = []
    while len(stack):
        index = stack.pop()
        index += 1
        while index < len(nums):
            if nums[index] not in permutation:
                break
            index += 1
        else:
            if len(permutation):
                permutation.pop()
            continue

        stack.append(index)
        stack.append(-1)
        permutation.append(nums[index])
        if len(permutation) == len(nums):
            permutations.append(list(permutation))
    return permutations

I'm just trying to understand the code above.

Have you tried stepping through it with a debugger? A good way to understand an algorithm. — FujiApple
– FujiApple, Commented Aug 17, 2016 at 4:09

ilim · Accepted Answer · 2020-06-05 05:55:46Z

As mentioned in the comments section to your question, debugging may provide a helpful way to understand what the code does. However, let me provide a high-level perspective of what your code does.

First of all, although there are no recursive calls to the function permute, the code your provided is effectively recursive, as all it does is keeping its own stack, instead of using the one provided by the memory manager of your OS. Specifically, the variable stack is keeping the recursive state, so to speak, that is passed from one recursive call to another. You could, and perhaps should, consider each iteration of the outer while loop in the permute function as a recursive call. If you do so, you will see that the outer while loop helps 'recursively' traverse each permutation of nums in a depth-first manner.

Noticing this, it's fairly easy to figure out what each 'recursive call' does. Basically, the variable permutation keeps the current permutation of nums which is being formed as while loop progresses. Variable permutations store all the permutations of nums that are found. As you may observe, permutations are updated only when len(permutation) is equal to len(nums) which can be considered as the base case of the recurrence relation that is being implemented using a custom stack. Finally, the inner while loop picks which element of nums to add to the current permutation(i.e. stored in variable permutation) being formed.

So that is about it, really. You can figure out what is exactly being done on the lines relevant to the maintenance of stack using a debugger, as suggested. As a final note, let me repeat that I, personally, would not consider this implementation to be non-recursive. It just so happens that, instead of using the abstraction provided by the OS, this recursive solution keeps its own stack. To provide a better understanding of how a proper non-recursive solution would be, you may observe the difference in recursive and iterative solutions to the problem of finding n^th Fibonacci number provided below. As you can see, the non-recursive solution keeps no stack, and instead of dividing the problem into smaller instances of it(recursion) it builds up the solution from smaller solutions. (dynamic programming)

def recursive_fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return recursive_fib(n-1) + recursive_fib(n-2)

def iterative_fib(n):
    f_0 = 0
    f_1 = 1
    for i in range(3, n):
        f_2 = f_1 + f_0
        f_0 = f_1
        f_1 = f_2
    return f_1

The previous algorithm is incorrect. Try recursive_fib(1) it would fail. It would generate recursive_fib(-1)? that was incorrect. Plus the recursive calls should be added not subtracted. I submitted an edit.

FujiApple · Accepted Answer · 2016-08-17 07:32:45Z

The answer from @ilim is correct and should be the accepted answer but I just wanted to add another point that wouldn't fit as a comment. Whilst I imagine you are studying this algorithm as an exercise it should be pointed out that a better way to proceed, depending on the size of the list, may be to user itertools's permutations() function:

print [x for x in itertools.permutations([1, 2, 3])]

Testing on my machine with a list of 11 items (39m permutations) took 1.7secs with itertools.permutations(x) but took 76secs using the custom solution above. Note however that with 12 items (479m permutations) the itertools solution blows up with a memory error. If you need to generate permutations of such size efficiently you may be better dropping to native code.

Collectives™ on Stack Overflow

Python Non-recursive Permutation

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related