Backtracking

Question 1

Permute string

Answer 1

def permutation(S):
    ##Your code here
    a=list(S)
    permute(a,0,len(S))

def permute(a,l,n):
    if l == n:
        print(toString(lst))
        return

for i in range(l,r):
    a[i],a[l] = a[l],a[i]
    permute(a,l+1,n)
    a[i],a[l] = a[l],a[i]

def toString(lst)
    return ''.join(lst)

Question 2

Print permutations in lexicographical order

Answer 2

First sort the string in decreasing order. Then print the string while we do not exhaust all the permutations.
To print the next permutation, first find the first character from right that is smaller than its right character. Then find the ceil element of first character in its right. Then swap the 2 and then reverse the right sub-list. This will give us sorted next permutation.

Question 3

Backtracking Concept

Answer 3

The concept is to prune the recursive tree by avoiding taking the next step if it is not safe. A check isSafe() should be applied before calling the next recursive call.

Question 4

Print all permutations but the ones containing ‘AB’

Answer 4

Apply isSafe() where 2 cases need to be checked.

1. If swapping l and i results in s[l-1] = A and s[l] = B.
2. If l=i-1 and s[l] = B and s[i]=A