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
– anand_v.singh, Commented Apr 4, 2019 at 3: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
– MFisherKDX, Commented Apr 4, 2019 at 3:33
... for example, compare the recursive and iterative psuedocode for Depth First Search from here. en.m.wikipedia.org/wiki/Depth-first_search — MFisherKDX
– MFisherKDX, Commented Apr 4, 2019 at 3:38

Aditya Santoso · Accepted Answer · 2019-04-04 04:05:05Z

1

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)

edited Apr 4, 2019 at 4:05

answered Apr 4, 2019 at 3:52

Aditya Santoso

1,0817 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

张安翔 · Accepted Answer · 2019-04-04 02:54:34Z

0

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

answered Apr 4, 2019 at 2:54

张安翔

1

Collectives™ on Stack Overflow

Python converting recursive permutation function to iterative

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related