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