| 14 | |
| 15 | |
| 16 | class AssignmentUsingBitmask: |
| 17 | def __init__(self,task_performed,total): |
| 18 | |
| 19 | self.total_tasks = total #total no of tasks (N) |
| 20 | |
| 21 | # DP table will have a dimension of (2^M)*N |
| 22 | # initially all values are set to -1 |
| 23 | self.dp = [[-1 for i in range(total+1)] for j in range(2**len(task_performed))] |
| 24 | |
| 25 | self.task = defaultdict(list) #stores the list of persons for each task |
| 26 | |
| 27 | #finalmask is used to check if all persons are included by setting all bits to 1 |
| 28 | self.finalmask = (1<<len(task_performed)) - 1 |
| 29 | |
| 30 | |
| 31 | def CountWaysUtil(self,mask,taskno): |
| 32 | |
| 33 | # if mask == self.finalmask all persons are distributed tasks, return 1 |
| 34 | if mask == self.finalmask: |
| 35 | return 1 |
| 36 | |
| 37 | #if not everyone gets the task and no more tasks are available, return 0 |
| 38 | if taskno > self.total_tasks: |
| 39 | return 0 |
| 40 | |
| 41 | #if case already considered |
| 42 | if self.dp[mask][taskno]!=-1: |
| 43 | return self.dp[mask][taskno] |
| 44 | |
| 45 | # Number of ways when we dont this task in the arrangement |
| 46 | total_ways_util = self.CountWaysUtil(mask,taskno+1) |
| 47 | |
| 48 | # now assign the tasks one by one to all possible persons and recursively assign for the remaining tasks. |
| 49 | if taskno in self.task: |
| 50 | for p in self.task[taskno]: |
| 51 | |
| 52 | # if p is already given a task |
| 53 | if mask & (1<<p): |
| 54 | continue |
| 55 | |
| 56 | # assign this task to p and change the mask value. And recursively assign tasks with the new mask value. |
| 57 | total_ways_util+=self.CountWaysUtil(mask|(1<<p),taskno+1) |
| 58 | |
| 59 | # save the value. |
| 60 | self.dp[mask][taskno] = total_ways_util |
| 61 | |
| 62 | return self.dp[mask][taskno] |
| 63 | |
| 64 | def countNoOfWays(self,task_performed): |
| 65 | |
| 66 | # Store the list of persons for each task |
| 67 | for i in range(len(task_performed)): |
| 68 | for j in task_performed[i]: |
| 69 | self.task[j].append(i) |
| 70 | |
| 71 | # call the function to fill the DP table, final answer is stored in dp[0][1] |
| 72 | return self.CountWaysUtil(0,1) |
| 73 | |