Assignment Problem Using BitMask
Given : In the assignment problem, you have N number of persons having some objects. Two or more persons could have the same object.
Objective : Finding the number of possible assignments of objects to persons such that no two persons have the same object in an assignment and each person has been assigned an object.
Example : In the below example we have three persons ( P0, P1, and P2 ) and we have three objects ( O0, O1 and O2 ).
In Scenario 1, we have 6 possible ways of assigning objects ( O0, O1, and O2 ) to persons ( P0, P1, and P2 ), and in
scenario 2, we have just 2 possible ways of assigning objects to persons.
Inefficient brute force
Consider a scenario where we have 20 persons and each person has 20 objects. We could try and use a brute force algorithm as follows:
1’st person could be assigned an object in : 20C1
2’nd person could be assigned an object in : 19C1
3’rd person could be assigned an object in : 18C1
…
20’th person could be assigned an object in : 1C1
Thus we have about 20C1 * 19C1 * 18C1 … 1C1 = 20 * 19 * 18 * 17 * …. 1 = 20 ! ways (i.e almost 2020 ways)
A brute force algorithm to count the number of ways for such a scenario would turn out to be highly inefficient and would time-out if the available time constraints for solving the problem are low.
Recursive approach
If there are 20 persons and 20 objects, then the possible states presented by the problem could be
[ set of persons ] * [ set of assigned objects ] i.e 2 20 * 2 20.
Example of a states with 3 persons and 3 objects would be :
[ 0 0 1 ] [ 0 1 0 ] i.e Person P0 has been assigned object O1.
[ 1 0 1 ] [ 1 1 0 ] i.e Person P2 has been assigned object O2 and Person P0 has been assigned object O1.
…
Since we only need to calculate the possible ways of assigning objects to persons ( such that no two persons have the same object in an assignment and each person has been assigned an object ), we could just limit the states to
[ set of persons ] * [ num of objects ] i.e 2 20 * 20.
Thus,
- If every person in the set has been assigned an object, we could say that 1 solution ( of many possible solutions ) has been found.
- If we run out of objects that could be assigned, we could say that 0 solutions ( no solution ) could be found.
Thus the recursive algorithm could be as below..
Given persons N, objects T.
int Count_Assignments ( Persons_That_Have_Been_Assigned_Objects, Object_Id )
-
Check if all the persons have been assigned object i.e
If (Persons_That_Have_Been_Assigned_Objects == N) then,
Return 1; as a possible solution has been found. -
If Object_Id > T (available objects) then,
Return 0; no solution could be found as all objects have been used. -
answer = 0
Skip assigning this object and try assigning the next object ( Object_Id + 1 ).
answer += Count_Assignments ( Persons_That_Have_Been_Assigned_Objects, Object_Id + 1 ) -
Try assigning the object_id to an eligible person
Check if a person could be assigned an object by iterating through the object to person mapping
If an eligible person has not been assigned an object, then assign the object to the person, then
ans += Count_Assignments ( Set the person bit in Persons_That_Have_Been_Assigned_Objects, Object_Id + 1 ) -
Return ans
Why bitmask
If we want to check that all the N persons have been assigned an object, we could use an array (boolean array) or we could just use a number ( ( 1 « N ) - 1 ).
Example : Say we have 3 persons, we could check if every person has been assigned an object simply by checking if the bit at a specific position
in the number ( 2 N - 1 ) has been set.
| Objects assigned to persons | Bit Mask | Number |
|---|---|---|
| P0 and P1 | 0 1 1 | 3 |
| P0 and P2 | 1 0 1 | 5 |
| P1 | 0 1 0 | 2 |
| P1, P2, and P3 | 1 1 1 ( all three bits are set indicating that all persons have been assigned an object ) | 7 |
Assigning an object to a person becomes very easy when using a bit mask.
Note : When none of the persons has been assigned an object we have a mask [ 0 0 0 ].
Example :
- If we want to assign an object to P0 we could set the last bit in the mask [ 0 0 0 ] as ( mask | 1 « person ) .
Thus we get ( 0 0 0 | 1 « 0 ) i.e 0 0 1. - If we want to assign an object to P1 we could set the last bit in the mask [ 0 0 0 ] as ( mask | 1 « person ).
Thus we get ( 0 0 0 | 1 « 1 ) i.e 0 1 0.
Checking if an object has been assigned to a person could be done in a slightly different way.
Example :
- If we have a mask [ 0 0 1 ] and we want to check if P1 has been assigned an object, we could check if
( mask & ( 1 « person ) > 0 ) i.e ( 0 0 1 & ( 1 « 1 ) > 0 )
as ( ( 0 0 1 ) & ( 0 1 0 ) == 0 ), person P1 has not been assigned any object.
C++ Assignment problem using bitmask. ( Number of objects is same as the number of persons )
Ref : Assignment problem
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
long long cache[1<<20+1][21];
class Assignment {
public:
int N;
bool matrix[21][21];
vector<vector<int>> obj_persons_mapping;
long long Count_Assignments (int person_mask, int obj_id) {
// All persons are assigned an object since all the bits in the
// person_mask are set. i.e 1 possible solution has been found.
if (person_mask == ( ( 1 << N ) - 1 ) ) {
return 1;
}
// As the object ids start with 0. Check if the
// object id is greater than the available objects
if (obj_id == N)
return 0;
if (cache[person_mask][obj_id] != -1)
return cache[person_mask][obj_id];
long long ans = 0;
ans = Count_Assignments(person_mask, obj_id + 1);
// Assign the objects to possible eligible persons.
for (const auto& person : obj_persons_mapping[obj_id]) {
// If the i'th bit in the person_mask is 0;
// it means that the i'th person has not got any object.
if ( (person_mask & (1<< person)) == 0 ) {
// Assign an object to the person.
ans += Count_Assignments( person_mask | ( 1 << person), obj_id + 1);
}
}
cache[person_mask][obj_id] = ans;
return ans;
}
};
int main() {
Assignment A;
int tcs;
cin >> tcs;
while (tcs--) {
memset(A.matrix, false, sizeof(A.matrix));
memset(cache, -1, sizeof(cache));
cin >> A.N;
A.obj_persons_mapping.resize(A.N);
for (int r=0; r<A.N; r++) {
for (int c=0; c<A.N; c++) {
cin >> A.matrix[r][c];
if (A.matrix[r][c]) {
// Store the list of persons that could be assigned a specific object
A.obj_persons_mapping[c].push_back(r);
}
}
}
int cnt = 0;
cout << "\nObjects to persons mapping..." << endl;
for (auto& persons : A.obj_persons_mapping) {
cout << "Object " << cnt++ << " : ";
for (auto& p : persons) {
cout << "P" << p << " ";
} cout << endl;
}
cout << "\nPossible assignments : " << A.Count_Assignments(0, 0) << endl;
A.obj_persons_mapping.clear();
}
return 0;
}
Output
$ ./a.out
1
3
1 1 1
1 1 1
1 1 1
Objects to persons mapping...
Object 0 : P0 P1 P2
Object 1 : P0 P1 P2
Object 2 : P0 P1 P2
Possible assignments : 6
$ ./a.out
1
3
1 0 1
1 1 0
0 1 1
Objects to persons mapping...
Object 0 : P0 P1
Object 1 : P1 P2
Object 2 : P0 P2
Possible assignments : 2
$ ./a.out
1
11
1 0 0 1 0 0 0 0 0 1 1
1 1 1 1 1 0 1 0 1 0 0
1 0 0 1 0 0 1 1 0 1 0
1 0 1 1 1 0 1 1 0 1 1
0 1 1 1 0 1 0 0 1 1 1
1 1 1 0 0 1 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 1
1 0 1 1 0 0 0 0 0 0 1
0 0 1 0 1 1 0 0 0 1 1
1 1 1 0 0 0 1 0 1 0 1
1 0 0 0 1 1 1 1 0 0 0
Objects to persons mapping...
Object 0 : P0 P1 P2 P3 P5 P7 P9 P10
Object 1 : P1 P4 P5 P9
Object 2 : P1 P3 P4 P5 P7 P8 P9
Object 3 : P0 P1 P2 P3 P4 P7
Object 4 : P1 P3 P6 P8 P10
Object 5 : P4 P5 P8 P10
Object 6 : P1 P2 P3 P6 P9 P10
Object 7 : P2 P3 P10
Object 8 : P1 P4 P9
Object 9 : P0 P2 P3 P4 P8
Object 10 : P0 P3 P4 P6 P7 P8 P9
Possible assignments : 7588
$ ./a.out
1
11
0 1 1 1 0 1 0 0 0 1 0
0 0 1 1 1 1 1 1 1 1 1
1 1 0 1 0 0 0 0 0 1 0
0 1 0 1 0 1 0 1 0 1 1
1 0 0 1 0 0 0 0 1 0 1
0 0 1 0 1 1 0 0 0 0 1
1 0 1 0 1 1 1 0 1 1 0
1 0 1 1 0 1 1 0 0 1 0
0 0 1 1 0 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 1 1
0 1 1 0 0 0 0 0 1 0 1
Objects to persons mapping...
Object 0 : P2 P4 P6 P7
Object 1 : P0 P2 P3 P9 P10
Object 2 : P0 P1 P5 P6 P7 P8 P10
Object 3 : P0 P1 P2 P3 P4 P7 P8
Object 4 : P1 P5 P6
Object 5 : P0 P1 P3 P5 P6 P7 P8
Object 6 : P1 P6 P7 P8
Object 7 : P1 P3 P8
Object 8 : P1 P4 P6 P8 P10
Object 9 : P0 P1 P2 P3 P6 P7 P8 P9
Object 10 : P1 P3 P4 P5 P8 P9 P10
Possible assignments : 7426