2020-03-19 12:33:50 +05:30

4.9 KiB
Raw Permalink Blame History

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.