4.9 KiB
Backtracking
Backtracking is a methodical way of trying out various sequences of decisions, until you find one that “works”. It is a systematic way to go through all the possible configurations of a search space.
- do
- recurse
- undo
Backtracking is easily implemented with recursion because:
- The run-time stack takes care of keeping track of the choices that got us to a given point.
- Upon failure we can get to the previous choice simply by returning a failure code from the recursive call.
Backtracking can help reduce the space complexity, because we're reusing the same storage.
Backtracking Algorithm: Backtracking is really quite simple--we “explore” each node, as follows:
To “explore” node N:
1. If N is a goal node, return “success”
2. If N is a leaf node, return “failure”
3. For each child C of N,
3.1. Explore C
3.1.1. If C was successful, return “success”
4. Return “failure”
Print all Permutations of a String
A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered string S into a one-to-one correspondence with S itself.
String: ABC
Permutations: ABC ACB BAC BCA CBA CAB
Total permutations = n!
def permute(S, i):
if i == len(S):
print(S)
for j in range(i, len(S)):
S[i], S[j] = S[j], S[i]
permute(S, i+1)
S[i], S[j] = S[j], S[i] # backtrack
Time Complexity: O(n*n!) because there are n! permutations and it requires O(n) to print a permutation.
Space Complexity: O(n)
Note: Output not in Lexicographic Order.
Print all Unique Permutations of a String
String: AAB Permutations: AAB ABA BAA
Basically, if we're swapping S[i] with S[j], but S[j] already occured earlier from S[i] .. S[j-1], then swapping will result in repetition.
def permute_distinct(S, i):
if i == len(S):
print(S)
for j in range(i, len(S)):
if S[j] in S[i:j]:
continue
S[i], S[j] = S[j], S[i]
permute_distinct(S, i+1)
S[i], S[j] = S[j], S[i] # backtrack
Time Complexity: O(n*n!)
Space Complexity: O(n)
Print Permutations Lexicographically
Given a string, print all permutations of it in sorted order.
For example, if the input string is “ABC”, then output should be “ABC, ACB, BAC, BCA, CAB, CBA”.
- Right shift the elements before making the recursive call.
- Left shift the elements while backtracking.
def permute(S, i):
if i == len(S):
print(S)
for j in range(i, len(S)):
S[i], S[j] = S[j], S[i]
permute(S, i+1)
S[i], S[j] = S[j], S[i] # backtrack
Time Complexity: O(n* n*n!)
Space Complexity: O(n)
Kth Permutation Sequence (Optional)
Given a string of length n containing lowercase alphabets only. You have to find the k-th permutation of string lexicographically.
\dfrac{k}{(n-1)!} will give us the index of the first digit. Remove that digit, and continue.
def get_perm(A, k):
perm = []
while A:
# get the index of current digit
div = factorial(len(A)-1)
i, k = divmod(k, div)
perm.append(A[i])
# remove handled number
del A[index]
return perm
Sorted Permutation Rank (Optional)
Given S, find the rank of the string amongst its permutations sorted lexicographically. Assume that no characters are repeated.
Input : 'acb'
Output : 2
Explanation:
The order permutations with letters 'a', 'c', and 'b' :
abc
acb
bac
bca
cab
cba
Hint: If the first character is X, all permutations which had the first character less than X would come before this permutation when sorted lexicographically.
Number of permutation with a character C as the first character = number of permutation possible with remaining N-1 character = (N-1)!
Approach: rank = number of characters less than first character * (N-1)! + rank of permutation of string with the first character removed
Lets say out string is “VIEW”.
Character 1 : 'V'
All permutations which start with 'I', 'E' would come before 'VIEW'.
Number of such permutations = 3! * 2 = 12
Lets now remove ‘V’ and look at the rank of the permutation ‘IEW’.
Character 2 : ‘I’
All permutations which start with ‘E’ will come before ‘IEW’
Number of such permutation = 2! = 2.
Now, we will limit ourself to the rank of ‘EW’.
Character 3:
‘EW’ is the first permutation when the 2 permutations are arranged.
So, we see that there are 12 + 2 = 14 permutations that would come before "VIEW".
Hence, rank of permutation = 15.