Storing results of a recursion

Question

I have this code, that will print all the permutations of a list :

def permute(iterable,fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            print iterable
        permute(iterable,fixed+1)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

Now I want to return this result instead of printing it, and the best way I found to do this is to store what's printed in a file, and then to read the file, extract the data and put it back in a list that I return :

import string
from random import *
import os

def randString(minLen=16,maxLen=32,charset=string.ascii_letters+string.digits):
    if(minLen>=maxLen):
        maxLen=minLen+1
    return "".join(choice(charset) for x in range(randint(minLen, maxLen)))

def permutations(iterable):
    def permute(iterable,f,fixed=0):
        for i in range(fixed,len(iterable)):
            iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
            if fixed==len(iterable)-1:
                f.write(''.join(iterable)+" ")
            permute(iterable,f,fixed+1)
            iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

    filename="."+randString()+".txt"
    f=open(filename,"w+")
    permute(list(iterable),f)
    f=open(filename,"r+")
    result=[]
    for i in f.read().split():
        result.append([])
        for j in i:
            result[-1].append(j)
    os.remove(filename)
    return result

The problem is : this makes the code a lot longer, and at least 3 times slower, since I store all the permutations in the file, and then I have to go again through each permutation to store it back in a list.

I tried to solve this problem by using global variables, or by passing the result list as parameter in the function, but it doesn't work (because of the recursion).

The following codes aren't working :

list as parameter

def permute2(iterable,fixed=0,permutations=[]):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            return iterable
        permutation = permute2(iterable,fixed+1)
        if permutation:
            permutations.append(permutation)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]
    return permutations

global variables

First

def permute(iterable,fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            global perms
            perms.append(iterable)
        permute(iterable,fixed+1)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

def permutations(iterable):
    global perms
    perms=[]
    permute(list(iterable))
    return perms

Second

def permute(iterable,fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            addPermutation(iterable)
        permute(iterable,fixed+1)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

def addPermutation(item):
    addPermutation.perms.append(item)

def permutations(iterable):
    addPermutation.perms=[]
    permute(list(iterable))
    return addPermutation.perms

These three bad codes pretty much all do the same thing : they returns a list containing n! times the first permutation.

Is there a way to solve this problem, or do I have to go with the code with the file ?

EDIT : After the comments of @DavidKemp and @uwain12345, I tried using a Class.

def permutations(iterable):
    class Permut:
        def __init__(self, iterable):
            self.iterable = list(iterable)
            self.permutations = []
            self.permute()

        def permute(self,fixed=0):
            for i in range(fixed,len(self.iterable)):
                self.iterable[fixed:] = [self.iterable[i]] + self.iterable[fixed:i] + self.iterable[i+1:]
                if fixed==len(self.iterable)-1:
                    self.permutations.append(self.iterable)
                self.permute(fixed+1)
                self.iterable[fixed:] = self.iterable[fixed+1:i+1] + [self.iterable[fixed]] + self.iterable[i+1:]

    p = Permut(list(iterable))
    return p.permutations

However I still get the exact same result as the codes above that were not working (n! times the first permutation).

Does https://stackoverflow.com/a/1988826/26479 solve your problem? — kͩeͣmͮpͥ ͩ, Mar 08 '18 at 15:27
Am I missing something? Why not use [`itertools.permutations`](https://docs.python.org/3/library/itertools.html#itertools.permutations)? — Patrick Haugh, Mar 08 '18 at 15:35
I'd try using a class. Then you can store your intermediate results in an instance variable. — uwain12345, Mar 08 '18 at 15:35
I am still getting the same result when I use a class, the only codes that works as expected are the two first ones. — Thomas, Mar 08 '18 at 16:04
@PatrickHaugh Yeah I know about itertools.permutations but I am trying to implement this code using a recursive backtracking algorithm — Thomas, Mar 08 '18 at 16:06

score 2 · Accepted Answer · answered Mar 08 '18 at 16:36

Your problem is that mutating the list iterable is a bad strategy. Changes made to iterbale will always be reflected, because they are all the same object. If we use tuples instead, we can avoid this. Here's the recursive permutation code I came up with:

def permute(iterable):
    iterable = tuple(iterable)
    if len(iterable) <= 1:
        yield iterable
        return
    for i, x in enumerate(iterable):
        for sub_permutation in permute(iterable[:i] + iterable[i+1:]):
            yield (x,) +  sub_permutation

score 1 · Answer 2 · answered Mar 08 '18 at 16:24

Unless this is an exercise, I recommend you follow Patrick Haugh's advice and use itertools.permutations. However, if you still insist on rolling your own then instead of print, use the yield keyword:

def permute(iterable, fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            yield iterable
        for e in permute(iterable,fixed+1):
            yield e
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

# Test out
for e in permute(['a', 'b', 'c']):
    print(e)

Output:

['a', 'b', 'c']
['a', 'c', 'b']
['b', 'a', 'c']
['b', 'c', 'a']
['c', 'a', 'b']
['c', 'b', 'a']

Notes

The yield statement will "return" one item at a time, but does not exit the function. This function returns a generator, so please read up on Python generators to learn more about it.

Consider the following block:

for element in permute(iterable, fixed + 1):
    yield element

if you are using Python 3, you can replace that block with

yield from permute(iterable, fixed + 1)

This works when printing each permutation, but try `list(permute([1, 2, 3]))`. Because we're yielding a mutated version of the same list, we end up with a list of identical permutations. — Patrick Haugh, Mar 08 '18 at 16:29

Storing results of a recursion

2 Answers2

Notes