CODEWITHSUNDEEP
pythonbacktracking
akhilc
akhilc

Reputation: 181

Python permutation using backtracking

I'm just trying to learn permutation using backtracking. I've written the following code but it stops after first output. 

def permutations(str_in, soFar):

    if len(str_in) != 0:
        for c in str_in:
            soFar.append(c)
            temp_str = str_in
            temp_str.remove(c)
            print temp_str, soFar
            permutations(temp_str, soFar)
    else:
        print soFar

inp = "ABCD"        
str_in = list(inp)
permutations(str_in, [])

This is the output I'm getting for this:

['B', 'C', 'D'] ['A']
['C', 'D'] ['A', 'B']
['D'] ['A', 'B', 'C']
[] ['A', 'B', 'C', 'D']
['A', 'B', 'C', 'D']

I'm sure this is something simple, but I'm not able to understand what mistake I'm making here.

Upvotes: 0

Views: 7718

Answers (2)

akhilc
akhilc

Reputation: 181

I rewrote it again and with some print commands in between I was able to reach the desired output. But still not entirely sure of the way it's working. I think it's mainly how python modifies a list with each call to the function. I had to assign temporary lists twice to make sure when tracing back the original lists are not modified. Anyway the following code is working.

def permute(String, SoFar):
    TempString = list(String)
    TempSoFar = list(SoFar)
    #print TempString, TempSoFar
    if TempString != []:
        for c in String:
            TStr = list(TempString)
            TSF = list(TempSoFar)
            TStr.remove(c)
            TSF.append(c)
            #print String, TStr, TSF
            permute(TStr, TSF)
    else:
        print "\nOut: ", TempSoFar, "\n"

permute(list("ABCD"),list(""))

Second solution using strings rather than lists, as mentioned in my comment below.

def permute(String, SoFar):
    #print "New Func Call: ", "SoFar: ", SoFar,"String: ", String, "\n"
    if String != "":
        for c in String:
            TS = String.replace(c,"")
            TSF = SoFar+c
            permute(TS, TSF)
            #print "A Call Finished", "SoFar: ", SoFar,"String: ", String, "TSF: ", TSF, "TS: ", TS
    else:
        print SoFar

permute("ABC","")

Upvotes: 0

Miket25
Miket25

Reputation: 1903

Here is Geeksforgeeks method, by Bhavya Jain, of permuting a string. The missing logic in your code is the recursive step on the sublists and a swapping behavior. Here is their visualization.

Geeksforgeeks visualization of recursive steps

def permute(a, l, r):
    if l==r:
        print toString(a)
    else:
        for i in xrange(l,r+1):
            a[l], a[i] = a[i], a[l]
            permute(a, l+1, r)
            a[l], a[i] = a[i], a[l] # backtrack

# Driver program to test the above function
string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n-1)

Output

['A', 'B', 'C']
['A', 'C', 'B']
['B', 'A', 'C']
['B', 'C', 'A']
['C', 'B', 'A']
['C', 'A', 'B']

Upvotes: 3

Related Questions