You are given an array of arrays $$$A$$$ containing integers of the range $$$[1, N]$$$. Now you need to select one element from every array present in $$$A$$$ such that no two elements are same i.e. you need to make a permutation of length $$$N$$$ such that element at $$$i_{th}$$$ index is present in the array $$$A_i$$$. Also find the number of permutations that satisfy this condition.
For example:
A = [
[1,2,5],
[3],
[2,4],
[1,4,5],
[1,3]
]
[2, 3, 4, 5, 1] will be a valid permutation for this case.
I think I have seen this problem as a subproblem in some questions, but I can not think of anything other than brute force.
Thanks.
what are the constraints on N ?
I don't remember that exactly, but I think it was something small like 15, so that pure brute force won't work but after some optimization it should work.
Here's an $$$O(N^2 \cdot 2^N)$$$ solution:
We'll use bitmask dp.
Intuitively, if we wanted to construct our permutation and we've already selected $$$i$$$ elements, what information matters?
Well, the elements, $$$A_1, \dots, A_i$$$ matter. However, the crucial observation here is that the order doesn't matter! The only thing that matters is what elements haven't been used.
Thus, we can compute:
$$$DP[i][MASK]$$$ = number of ways to select first $$$i$$$ numbers such that we have used the numbers in bitmask $$$MASK$$$. The $$$j$$$ th bit of $$$MASK$$$, $$$MASK_j = 1$$$ if we have used $$$j$$$ and $$$0$$$ otherwise.
The base case is: $$$DP[0][0] = 1$$$.
Our transitions would be:
$$$DP[i+1][MASK + 2^j] \mathrel{+}= DP[i][MASK]$$$
for all $$$j$$$ such that $$$MASK_j = 0$$$ and $$$j$$$ is in the $$$i+1$$$ th array.