Python permutation using backtracking

Question

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.

There are 2 issues, with same root cause here. - `temp_str` is designed to be a _copy_ of the input list, but it just takes the reference, so it quicky exhausts the input and recursion stops - `soFar` should be reset after being printed, or the result is incorrect (contains previous results as well). I'm not posting a solution because this still yields duplicates. Not sure it's the proper algorithm, but it's better. — Jean-François Fabre, Aug 18 '17 at 18:49
I'm trying to generate all possible permuations such as [A, B, C, D] then [A, B, D, C] and so on. — akhilc, Aug 18 '17 at 18:50
@Jean-FrançoisFabre I'm trying to learn this backtracking method. I don't want to use any inbuilt functions. — akhilc, Aug 18 '17 at 18:55
It's not permuting the sublists during the descent i.e. there's no swapping process. The characters' position are just going in a circle. — Miket25, Aug 18 '17 at 19:15

score 3 · Answer 1 · answered Aug 18 '17 at 19:21

3

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.

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']

answered Aug 18 '17 at 19:21

Miket25

1,895
3
15
29

I'm following a youtube lecture series for the logic that I'm trying to implement. In my code swapping is supposed to happen with the for loop implementation. Suppose `SoFar = ['A', 'B']` and `temp_str = ['C', 'D']`. Then loop should happen over `'C'` and `'D'`. In second iteration it will choose `'D'` and append it to `SoFar`. – akhilc Aug 19 '17 at 03:03
@akhilc Perhaps you should see if you're passing these list by reference or by value. An mutation on a list somewhere on a recursive call **should not** affect the previous call's list, unless explicitly stated. – Miket25 Aug 19 '17 at 03:12

akhilc · Answer 2 · 2017-08-20T08:14:33.813

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","")

Just in case someone stumbles upon similar issue, adding another solution. Reading up a bit more, I understood that lists are mutable so that's the reason I had to reassign it twice to make sure they're not altered when going to subsequent recursive function call. So I again rewrote, but this time function arguments are strings, which are immutable. Voila, it works without reassigning again. — akhilc, Aug 20 '17 at 08:12

Python permutation using backtracking

2 Answers2

Linked