bitmask Algorithm
The bitmask algorithm is a powerful technique used in computer programming, particularly in solving complex computational problems. It is based on the manipulation of individual bits in a binary number, using bitwise operations such as AND, OR, XOR, and NOT. Bitmasking is often employed in problems that involve combinatorics, dynamic programming, and optimization, where the state of certain elements needs to be tracked or controlled. The primary advantage of using bitmasking is that it allows for efficient representation and manipulation of data, as each bit can represent a separate state or piece of information. This reduces both the time and space complexity of the algorithm, enabling faster and more efficient solutions for complex problems.
One common application of the bitmask algorithm is in subset generation and manipulation. By assigning each element of a set to a unique bit position, all possible subsets can be represented as binary numbers, where a '1' indicates the presence of an element in the subset and a '0' represents its absence. This compact representation allows for quick and easy operations on subsets, such as intersection, union, or complement, using the corresponding bitwise operations. Furthermore, bitmasking can be used to optimize dynamic programming problems by storing intermediate results in a compact manner, which reduces the need for redundant computations and speeds up the overall process. Overall, the bitmask algorithm is a versatile tool that greatly enhances the efficiency and effectiveness of problem-solving in various domains of computer programming.
"""
This is a Python implementation for questions involving task assignments between people.
Here Bitmasking and DP are used for solving this.
Question :-
We have N tasks and M people. Each person in M can do only certain of these tasks. Also
a person can do only one task and a task is performed only by one person.
Find the total no of ways in which the tasks can be distributed.
"""
from collections import defaultdict
class AssignmentUsingBitmask:
def __init__(self, task_performed, total):
self.total_tasks = total # total no of tasks (N)
# DP table will have a dimension of (2^M)*N
# initially all values are set to -1
self.dp = [
[-1 for i in range(total + 1)] for j in range(2 ** len(task_performed))
]
self.task = defaultdict(list) # stores the list of persons for each task
# final_mask is used to check if all persons are included by setting all bits
# to 1
self.final_mask = (1 << len(task_performed)) - 1
def CountWaysUtil(self, mask, task_no):
# if mask == self.finalmask all persons are distributed tasks, return 1
if mask == self.final_mask:
return 1
# if not everyone gets the task and no more tasks are available, return 0
if task_no > self.total_tasks:
return 0
# if case already considered
if self.dp[mask][task_no] != -1:
return self.dp[mask][task_no]
# Number of ways when we don't this task in the arrangement
total_ways_util = self.CountWaysUtil(mask, task_no + 1)
# now assign the tasks one by one to all possible persons and recursively
# assign for the remaining tasks.
if task_no in self.task:
for p in self.task[task_no]:
# if p is already given a task
if mask & (1 << p):
continue
# assign this task to p and change the mask value. And recursively
# assign tasks with the new mask value.
total_ways_util += self.CountWaysUtil(mask | (1 << p), task_no + 1)
# save the value.
self.dp[mask][task_no] = total_ways_util
return self.dp[mask][task_no]
def countNoOfWays(self, task_performed):
# Store the list of persons for each task
for i in range(len(task_performed)):
for j in task_performed[i]:
self.task[j].append(i)
# call the function to fill the DP table, final answer is stored in dp[0][1]
return self.CountWaysUtil(0, 1)
if __name__ == "__main__":
total_tasks = 5 # total no of tasks (the value of N)
# the list of tasks that can be done by M persons.
task_performed = [[1, 3, 4], [1, 2, 5], [3, 4]]
print(
AssignmentUsingBitmask(task_performed, total_tasks).countNoOfWays(
task_performed
)
)
"""
For the particular example the tasks can be distributed as
(1,2,3), (1,2,4), (1,5,3), (1,5,4), (3,1,4),
(3,2,4), (3,5,4), (4,1,3), (4,2,3), (4,5,3)
total 10
"""
