Use Backtracking to find all Palindromic Bitlists of a given length in Python
By Manan KumarIn this tutorial, we are going to take up the task of finding all the palindromic bitlists of a given length ‘n’ using the backtracking approach in Python. For this purpose, we first need to know what bitlists are.
A bitlist, as is evident from the name, is a list of bits or binary digits, i.e. 0 and 1. So any list of 0’s and 1’s is a bitlist.
Thus, a palindromic bitlist is a bitlist that is also a palindrome, i.e., it is the same in both directions, forward and backward.
Now let’s talk about the approach that we are going to take, i.e.backtracking.
What is Backtracking?
The backtracking approach is a way of solving different kinds of problems by building upon the solution with every feasible option, i.e., removing the options that do not meet our required conditions.
A general approach for backtracking is as follows:
- Find a representation of partial solutions such that all valid options to be augmented to a partial solution can be identified as well as when a partial solution becomes a complete solution.
- The task now is to find all the solutions that can be reached from a partial solution to a complete solution via a series of valid decisions.
- Construct all complete solutions via partial solutions using recurrence relation: sols(part)=sols(part+[a1])+…+sols(part+[ak]) where [a1,…,ak] are all valid options to augment part.
For any backtracking problem, the general implementation in Python would look like this:
def solutions(completed, options, partial=[]):
if completed(partial):
return [partial]
else:
res = []
for o in options(partial):
augmented = partial+[o]
res += solutions(completed, options, augmented)
return res
def problem_to_be_solved(n):
def options(partial):
# options to be implemented
def complete(partial): return len(partial) == n
return solutions(complete, options)In the above code, the only thing that needs to be implemented is the options function. The above code works in the following manner:
- It starts off with an empty partial solution,
- It keeps building upon the partial solution using the options function which defines what solutions are feasible and removes the options that do not meet our requirement.
- As soon as the partial solution meets the ‘completed’ requirement, it is appended to our final ‘solutions’.
How to find all palindromic bitlists of a given length using Backtracking?
For our task, we’ll use the above general implementation itself and define our ‘options’ function like this:
- If the length of our partial solution is less than half the given length ‘n’ (in case of even ‘n’/ +1 in case of odd ‘n’): then we have both our options 0 and 1 feasible to be added to the partial solution.
- Otherwise, we can only use the bit that was at the index [n-len(partial)-1], (for example: for n = 3, and partial = [0,0] we can’t use ‘1’ for the next element as it will not satisfy our condition of palindromic bitlists).
Implementing the code in Python
def solutions(completed, options, partial=[]):
if completed(partial):
return [partial]
else:
res = []
for o in options(partial):
augmented = partial+[o]
res += solutions(completed, options, augmented)
return res
def palindromic_bitlists(n):
def options(partial):
if len(partial)<n//2+n%2:
return [0,1]
return [partial[n-len(partial)-1]]
def complete(partial): return len(partial) == n
return solutions(complete, options, [])Let’s run an example:
palindromic_bitlists(5)
Output:
[[0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 0, 0, 0, 1], [1, 0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1]]
Thank you for sparing your valuable time in order to read this article. You can check out other articles as well:
Leave a Reply