Python converting recursive permutation function to iterative

Question

I have an unknown number of Integer variables say that can range from [0,9] I want to iterate over all permutations of these values.

If the number of variables was constant, it would be easy to write nested for loops. I came up with a recursive function that does what I want, but was curious if there was a way to do it iteratively.

def nested(array,index):
    n = len(array)
    for i in range(10):
        array[n-index]=i
        #len(array-1) end of array
        if(index == 1):
            print(array)
            #do something later
        else:
            nested(array,index-1)

#generate all permutations, change n to change size of list.            
n = 4
array = [0]*n
nested(array,len(array))

I tried using the so called "Simple Method" found here -> http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html But I couldn't get it to work.

Please be more specific in what didn't work in the blog that you have linked. As far as I can see, the post covers iteration to recursion well, please update the question with your effort. — anand_v.singh, Apr 04 '19 at 03:09
There's no real "secret" here. Most of what is explained in that blog post applies to linear recursive algorithms (search for an item in a linked list), as opposed to branching recursive algorithms (search for a path in a graph). The permutations problem is the latter (a tree). The easiest way to convert a recursive algorithm of this form to an iterative version is to use a stack / queue data structure. Pop an element from the stack. Operate on it. Push the branch nodes on it. Quit when the stack is empty. — MFisherKDX, Apr 04 '19 at 03:33
... for example, compare the recursive and iterative psuedocode for Depth First Search from here. https://en.m.wikipedia.org/wiki/Depth-first_search — MFisherKDX, Apr 04 '19 at 03:38

Aditya Santoso · Accepted Answer · 2019-04-04T04:05:05.613

As was mentioned by another commenter, the key is to simulate your tail recursion using a stack.

Take note I append() a tuple of (array, index) into the stack, which mirrors the call to recursive function in your original recursive solution. At the start of the iteration, it does stack.pop(), which mimics the body of your recursive function. Recursive call becomes stack.append().

def nested(array):
    stack = []
    n = len(array)
    stack.append((array.copy(), n))
    while(stack):
        array, index = stack.pop()        
        for i in range(10):
            array[n-index]=i
            #len(array-1) end of array
            if(index == 1):
                print(array)
                #do something later
            else:
                stack.append((array.copy(), index-1)) 

#generate all permutations, change n to change size of list.            
n = 4
array = [0]*n
nested(array)

score 0 · Answer 2 · answered Apr 04 '19 at 02:54

0

Please refer to itertools. There is a Class "permutations" that could solve your problem perfectly.

answered Apr 04 '19 at 02:54

张安翔

1

Python converting recursive permutation function to iterative

2 Answers2