CODEWITHSUNDEEP
pythonperformancetime
swarajd
swarajd

Reputation: 1007

How to decrease running time of this particular solution?

I am trying to write a piece of code that will generate a permutation, or some series of characters that are all different in a recursive fashion. 

def getSteps(length, res=[]):
    if length == 1: 
        if res == []:
            res.append("l")
            res.append("r")
            return res
        else:
            for i in range(0,len(res)):
                res.append(res[i] + "l")
                res.append(res[i] + "r")
            print(res)
            return res
    else:
        if res == []:
            res.append("l")
            res.append("r")
            return getSteps(length-1,res)
        else:
            for i in range(0,len(res)):
                res.append(res[i] + "l")
                res.append(res[i] + "r")
            print(res)
            return getSteps(length-1,res)

def sanitize(length, res):
    return [i for i in res if len(str(i)) == length]

print(sanitize(2,getSteps(2)))

So this would return

"LL", "LR", "RR, "RL" or some permutation of the series.

I can see right off the bat that this function probably runs quite slowly, seeing as I have to loop through an entire array. I tried to make the process as efficient as I could, but this is as far as I can get. I know that some unnecessary things happen during the run, but I don't know how to make it much better. So my question is this: what would I do to increase the efficiency and decrease the running time of this code?

edit = I want to be able to port this code to java or some other language in order to understand the concept of recursion rather than use external libraries and have my problem solved without understanding it.

Upvotes: 2

Views: 151

Answers (3)

Tim Peters
Tim Peters

Reputation: 70592

Is there a way to combine the binary approach and a recursive approach?

Yes, and @gribbler came very close to that in the post to which that comment was attached. He just put the pieces together in "the other order".

How can you construct all the bitstrings of length n, in increasing order (when viewed as binary integers)? Well, if you already have all the bitstrings of length n-1, you can prefix them all with 0, and then prefix them all again with 1. It's that easy.

def f(n):
    if n == 0:
        return [""]
    return [a + b for a in "RL" for b in f(n-1)]

print(f(3))

prints

['RRR', 'RRL', 'RLR', 'RLL', 'LRR', 'LRL', 'LLR', 'LLL']

Replace R with 0, and L with 1, and you have the 8 binary integers from 0 through 7 in increasing order.

Upvotes: 1

John La Rooy
John La Rooy

Reputation: 304157

Your design is broken. If you call getSteps again, res won't be an empty list, it will have garbage left over from the last call in it.

I think you want to generate permutations recursively, but I don't understand where you are going with the getSteps function

Here is a simple recursive function

def fn(x):
    if x==1:
        return 'LR'
    return [j+i for i in fn(x-1) for j in "LR"]

Upvotes: 2

Atra Azami
Atra Azami

Reputation: 2245

You should look into itertools. There is a function there called permutations which does exactly what you want to achieve here.

Upvotes: 0

Related Questions