Repository: TheAlgorithms/Java
Pull request #5792 (2024-10-14 03:57:23)

feat: Add `AssignmentUsingBitmask` new algorithm with Junit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5792?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 64.28%. Comparing base [(`213fd5a`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/213fd5a4931ba1cb74fed76ff97043ae34ff174b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`375db65`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/375db65f743aafabcc369aca0997c665289b4d07?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5792      +/-   ##
============================================
+ Coverage     64.21%   64.28%   +0.06%     
- Complexity     4216     4229      +13     
============================================
  Files           588      589       +1     
  Lines         16426    16455      +29     
  Branches       3170     3178       +8     
============================================
+ Hits          10548    10578      +30     
  Misses         5448     5448              
+ Partials        430      429       -1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5792?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index e7a08a12..e511ab40 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -262,6 +262,7 @@
             * [TilingProblem](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/TilingProblem.java)
           * dynamicprogramming
             * [Abbreviation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/Abbreviation.java)
+            * [AssignmentUsingBitmask](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmask.java)
             * [BoardPath](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/BoardPath.java)
             * [BoundaryFill](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/BoundaryFill.java)
             * [BruteForceKnapsack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/BruteForceKnapsack.java)
@@ -866,6 +867,7 @@
             * [TilingProblemTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/TilingProblemTest.java)
           * dynamicprogramming
             * [AbbreviationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/AbbreviationTest.java)
+            * [AssignmentUsingBitmaskTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmaskTest.java)
             * [BoardPathTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/BoardPathTest.java)
             * [BoundaryFillTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/BoundaryFillTest.java)
             * [BruteForceKnapsackTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/BruteForceKnapsackTest.java)
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmask.java b/src/main/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmask.java
new file mode 100644
index 00000000..5a894ca0
--- /dev/null
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmask.java
@@ -0,0 +1,91 @@
+package com.thealgorithms.dynamicprogramming;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.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
+ */
+public final class AssignmentUsingBitmask {
+
+    private final int totalTasks;
+    private final int[][] dp;
+    private final List<List<Integer>> task;
+    private final int finalMask;
+
+    /**
+     * 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.
+     */
+    public AssignmentUsingBitmask(List<List<Integer>> taskPerformed, int total) {
+        this.totalTasks = total;
+        this.dp = new int[1 << taskPerformed.size()][total + 1];
+        for (int[] row : dp) {
+            Arrays.fill(row, -1);
+        }
+
+        this.task = new ArrayList<>(totalTasks + 1);
+        for (int i = 0; i <= totalTasks; i++) {
+            this.task.add(new ArrayList<>());
+        }
+
+        // Final mask to check if all persons are included
+        this.finalMask = (1 << taskPerformed.size()) - 1;
+
+        // Fill the task list
+        for (int i = 0; i < taskPerformed.size(); i++) {
+            for (int j : 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.
+     */
+    private int countWaysUntil(int mask, int taskNo) {
+        if (mask == finalMask) {
+            return 1;
+        }
+        if (taskNo > totalTasks) {
+            return 0;
+        }
+        if (dp[mask][taskNo] != -1) {
+            return dp[mask][taskNo];
+        }
+
+        int totalWays = countWaysUntil(mask, taskNo + 1);
+
+        // Assign tasks to all possible persons
+        for (int p : 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;
+        return dp[mask][taskNo];
+    }
+
+    /**
+     * Counts the total number of ways to distribute tasks among persons.
+     *
+     * @return the total number of ways to distribute tasks.
+     */
+    public int countNoOfWays() {
+        return countWaysUntil(0, 1);
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmaskTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmaskTest.java
new file mode 100644
index 00000000..0258f395
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/AssignmentUsingBitmaskTest.java
@@ -0,0 +1,54 @@
+package com.thealgorithms.dynamicprogramming;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.Arrays;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+public final class AssignmentUsingBitmaskTest {
+
+    @Test
+    public void testCountNoOfWays() {
+        int totalTasks = 5;
+
+        List<List<Integer>> taskPerformed = Arrays.asList(Arrays.asList(1, 3, 4), Arrays.asList(1, 2, 5), Arrays.asList(3, 4));
+
+        AssignmentUsingBitmask assignment = new AssignmentUsingBitmask(taskPerformed, totalTasks);
+        int ways = assignment.countNoOfWays();
+        assertEquals(10, ways);
+    }
+
+    @Test
+    public void testNoPossibleAssignments() {
+        int totalTasks = 3;
+
+        List<List<Integer>> taskPerformed = Arrays.asList(Arrays.asList(2), Arrays.asList(3));
+
+        AssignmentUsingBitmask assignment = new AssignmentUsingBitmask(taskPerformed, totalTasks);
+        int ways = assignment.countNoOfWays();
+        assertEquals(1, ways);
+    }
+
+    @Test
+    public void testSinglePersonMultipleTasks() {
+        int totalTasks = 3;
+
+        List<List<Integer>> taskPerformed = Arrays.asList(Arrays.asList(1, 2, 3));
+
+        AssignmentUsingBitmask assignment = new AssignmentUsingBitmask(taskPerformed, totalTasks);
+        int ways = assignment.countNoOfWays();
+        assertEquals(3, ways);
+    }
+
+    @Test
+    public void testMultiplePeopleSingleTask() {
+        int totalTasks = 1;
+
+        List<List<Integer>> taskPerformed = Arrays.asList(Arrays.asList(1), Arrays.asList(1));
+
+        AssignmentUsingBitmask assignment = new AssignmentUsingBitmask(taskPerformed, totalTasks);
+        int ways = assignment.countNoOfWays();
+        assertEquals(0, ways);
+    }
+}