1+ """
2+
3+ This is a python implementation for questions involving task assignments between people.
4+ Here Bitmasking and DP are used for solving this.
5+
6+ Question :-
7+ 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.
8+ Find the total no of ways in which the tasks can be distributed.
9+
10+
11+ """
12+ from __future__import print_function
13+ from collections import defaultdict
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+
74+
75+ if __name__ == '__main__' :
76+
77+ total_tasks = 5 #total no of tasks (the value of N)
78+
79+ #the list of tasks that can be done by M persons.
80+ task_performed = [
81+ [1 ,3 ,4 ],
82+ [1 ,2 ,5 ],
83+ [3 ,4 ]
84+ ]
85+ print (AssignmentUsingBitmask (task_performed ,total_tasks ).countNoOfWays (task_performed ))
86+ """
87+ For the particular example the tasks can be distributed as
88+ (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)
89+ total 10
90+ """