Count ways to select N pairs of candies of distinct colors (Dynamic Programming + Bitmasking)

Count ways to select N pairs of candies of distinct colors (Dynamic Programming + Bitmasking)

Given an integer N representing the number of red and blue candies and a matrix mat[][] of size N * N, where mat[i][j] = 1 represents the existence of a pair between i^th red candy and j^th blue candy, the task is to find the count of ways to select N pairs of candies such that each pair contains distinct candies of different colors.

Examples:

Input: N = 2, mat[][] = { { 1, 1 }, { 1, 1 } }
Output: 2
Explanation:
Possible ways to select N (= 2) pairs of candies are { { (1, 1), (2, 2) }, { (1, 2), (2, 1) } }.
Therefore, the required output is 2.

Input: N = 3, mat[][] = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } }
Output: 3
Explanation:
Possible ways to select N (= 3) pairs of candies are: { { (1, 2), (2, 1), (3, 3) }, { (1, 2), (2, 3), (3, 1) }, { (1, 3), (2, 1), (3, 2) } }
Therefore, the required output is 2.

Naive Approach: The simplest approach to solve this problem is to generate all possible permutations of N pairs containing distinct candies of a different colors. Finally, print the count obtained.

Below is the implementation of the above approach:

Python3

def numOfWays(a, n, i = 0, blue = []):                if i == n:         return 1                  count = 0             for j in range(n):                     if mat[i][j] == 1 and j not in blue:             count += numOfWays(mat, n, i + 1,                                  blue + [j])                                        return count    if __name__ == "__main__":     n = 3     mat = [ [0, 1, 1],             [1, 0, 1],              [1, 1, 1] ]     print(numOfWays(mat, n))

Time complexity: O(N!)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized using Dynamic programming with Bit masking. Instead of generating all permutations of N blue candies, for every red candy, use a mask, where j^th bit of mask checks if j^th blue candy is available for selecting in the current pair or not.
The recurrence relation to solve the problem is as follows:

If K^th bit of mask is unset and mat[i][k] = 1:
dp[i + 1][j | (1 k)] += dp[i][j]

where, (j | (1 k)) marks the kth blue candy as selected.
dp[i][j] = Count of ways to make pairs between i red candy and N blue candies, where j is a permutation of N bit number range from 0 to 2^N – 1).

Follow the steps below to solve the problem:

• Initialize a 2D array, say dp[][], where dp[i][j] stores the count of ways to make pairs between i red candies and N blue candies. j represents a permutation of N bit number range from 0 to 2^N-1.
• Use the above recurrence relation and fill all possible dp states of the recurrence relation.
• Finally, print the dp state where there are N red candies and N blue candies are selected, i.e. dp[i][2ⁿ-1].

Below is the implementation of the above approach:

Python3

def numOfWays(a, n):                     dp = [[0]*((1 << n)+1) for _ in range(n + 1)]                  dp[0][0] = 1             for i in range(n):                                       for j in range(1 << n):                if dp[i][j] == 0:                 continue                                for k in range(n):                                                      mask = 1 << k                                                                      if not(mask & j) and a[i][k]:                     dp[i + 1][j | mask] += dp[i][j]                                                                        return dp[n][(1 << n)-1]          if __name__ == "__main__":     n = 3     mat = [[0, 1, 1],            [1, 0, 1],            [1, 1, 1]]     print(numOfWays(mat, n))

Time Complexity:O(N² * 2^N)
Auxiliary Space: O(N * 2^N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)