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 dp table will have a dimension of 2mn initially all values are set to 1 finalmask is used to check if all persons are included by setting all bits to 1 if mask self finalmask all persons are distributed tasks return 1 if not everyone gets the task and no more tasks are available return 0 if case already considered number of ways when we don t this task in the arrangement now assign the tasks one by one to all possible persons and recursively assign for the remaining tasks if p is already given a task assign this task to p and change the mask value and recursively assign tasks with the new mask value save the value store the list of persons for each task call the function to fill the dp table final answer is stored in dp01 the list of tasks that can be done by m persons 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 total no of tasks n dp table will have a dimension of 2 m n initially all values are set to 1 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 if mask self finalmask all persons are distributed tasks return 1 if not everyone gets the task and no more tasks are available return 0 if case already considered number of ways when we don t this task in the arrangement now assign the tasks one by one to all possible persons and recursively assign for the remaining tasks if p is already given a task assign this task to p and change the mask value and recursively assign tasks with the new mask value save the value store the list of persons for each task call the function to fill the dp table final answer is stored in dp 0 1 total no of tasks the value of n the list of tasks that can be done by m persons 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
from collections import defaultdict


class AssignmentUsingBitmask:
    def __init__(self, task_performed, total):
        self.total_tasks = total  

        
        
        self.dp = [
            [-1 for i in range(total + 1)] for j in range(2 ** len(task_performed))
        ]

        self.task = defaultdict(list)  

        
        
        self.final_mask = (1 << len(task_performed)) - 1

    def count_ways_until(self, mask, task_no):
        
        if mask == self.final_mask:
            return 1

        
        if task_no > self.total_tasks:
            return 0

        
        if self.dp[mask][task_no] != -1:
            return self.dp[mask][task_no]

        
        total_ways_util = self.count_ways_until(mask, task_no + 1)

        
        
        if task_no in self.task:
            for p in self.task[task_no]:
                
                if mask & (1 << p):
                    continue

                
                
                total_ways_util += self.count_ways_until(mask | (1 << p), task_no + 1)

        
        self.dp[mask][task_no] = total_ways_util

        return self.dp[mask][task_no]

    def count_no_of_ways(self, task_performed):
        
        for i in range(len(task_performed)):
            for j in task_performed[i]:
                self.task[j].append(i)

        
        return self.count_ways_until(0, 1)


if __name__ == "__main__":
    total_tasks = 5  

    
    task_performed = [[1, 3, 4], [1, 2, 5], [3, 4]]
    print(
        AssignmentUsingBitmask(task_performed, total_tasks).count_no_of_ways(
            task_performed
        )
    )