CODEWITHSUNDEEP
pythonalgorithmbacktracking
KangJiYoung13
KangJiYoung13

Reputation: 330

Backtracking permuting a list

I am trying to permute a list but I cannot do it, it goes infinite cycle. I tried different things but somehow the only thing that it shows me is 1 2 3 ... 1 2 3 etc

This is the code:

def prints(v,k):
    s = ''
    for i in range(k + 1):
        s += str(v[i]) + ' '
    print(s)   

def continuare(v,k):
    ok = True
    for i in range(k):
        if v[i] == v[k]:
            ok = False
            break
    return ok

def back(v,a):
    k = 0
    caut = False
    while k>-1:
        caut = False        
        pos = 0
        while pos < len(a) and caut == False:
                v[k] = a[pos]
                pos += 1
                if continuare(v,k):
                    caut = True
        if caut == False:
            k -= 1
        elif k == len(a) - 1:
            prints(v,k)
        else:
            k += 1


a = [1,2,3]
v = []
for x in range(len(a)):
    v.append(a[0])
back(v,a)

Upvotes: 1

Views: 3926

Answers (1)

Alex Martelli
Alex Martelli

Reputation: 881785

Here's a trivial Python transcription from http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ :

def swap(a, i, j):
    a[i], a[j] = a[j], a[i]

def permute(a, i, n):
    if i == n:
        print(a)
        return
    for j in range(i, n+1):
        swap(a, i, j)
        permute(a, i+1, n)
        swap(a, i, j)  # backtrack

def main():
    a = list('ABC')
    permute(a, 0, 2)

if __name__ == '__main__':
    main()

I'd rather have permute be a generator yielding the permutations, with main looping on them and printing them, but this may be closer to the C original and thus easier to follow. Note that one difference is a must: what's being permuted here is a list, not a string as in the C original, because strings are immutable in Python (so swap would require substantially different logic, returning the "string with swapped characters" rather than being able to work in-place as the "backtracking" logic requires).

Upvotes: 2

Related Questions