AssignmentUsingBitmask.java

packagecom.thealgorithms.dynamicprogramming;

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.List;

/**
 * The AssignmentUsingBitmask class is used to calculate the total number of ways
 * tasks can be distributed among people, given specific constraints on who can perform which tasks.
 * The approach uses bitmasking and dynamic programming to efficiently solve the problem.
 *
 * @author Hardvan
 */
publicfinalclassAssignmentUsingBitmask {

privatefinalinttotalTasks;
privatefinalint[][] dp;
privatefinalList<List<Integer>> task;
privatefinalintfinalMask;

/**
 * Constructor for the AssignmentUsingBitmask class.
 *
 * @param taskPerformed a list of lists, where each inner list contains the tasks that a person can perform.
 * @param total the total number of tasks.
 */
publicAssignmentUsingBitmask(List<List<Integer>> taskPerformed, inttotal) {
this.totalTasks = total;
this.dp = newint[1 << taskPerformed.size()][total + 1];
for (int[] row : dp) {
Arrays.fill(row, -1);
 }

this.task = newArrayList<>(totalTasks + 1);
for (inti = 0; i <= totalTasks; i++) {
this.task.add(newArrayList<>());
 }

// Final mask to check if all persons are included
this.finalMask = (1 << taskPerformed.size()) - 1;

// Fill the task list
for (inti = 0; i < taskPerformed.size(); i++) {
for (intj : taskPerformed.get(i)) {
this.task.get(j).add(i);
 }
 }
 }

/**
 * Counts the ways to assign tasks until the given task number with the specified mask.
 *
 * @param mask the bitmask representing the current state of assignments.
 * @param taskNo the current task number being processed.
 * @return the number of ways to assign tasks.
 */
privateintcountWaysUntil(intmask, inttaskNo) {
if (mask == finalMask) {
return1;
 }
if (taskNo > totalTasks) {
return0;
 }
if (dp[mask][taskNo] != -1) {
returndp[mask][taskNo];
 }

inttotalWays = countWaysUntil(mask, taskNo + 1);

// Assign tasks to all possible persons
for (intp : task.get(taskNo)) {
// If the person is already assigned a task
if ((mask & (1 << p)) != 0) {
continue;
 }
totalWays += countWaysUntil(mask | (1 << p), taskNo + 1);
 }

dp[mask][taskNo] = totalWays;
returndp[mask][taskNo];
 }

/**
 * Counts the total number of ways to distribute tasks among persons.
 *
 * @return the total number of ways to distribute tasks.
 */
publicintcountNoOfWays() {
returncountWaysUntil(0, 1);
 }
}