Suppose, I have given N distinct pairs(x, y) of elements. Choose k pairs from these elements every time. Count the chosen ways when number of distinct value is equal to R in the chosen pairs.
Constraints: N = 100 K >= 50 k <= R <= 2K.
Example: Given, N = 6, k = 3, r = 4.
Pairs: a. (1, 2) b. (1, 3) c. (2, 4) d. (2, 5) e. (3, 4) f. (4, 5)
Now if we choose pairs (a, b, e), the distinct values are:- S = {1, 2, 3, 4} Number of Distinct values |S| = 4 and |S| == R. So, this is a valid combination.
If we choose pairs (c, d, e}, the distinct values are:- S = {2, 3, 4, 5} Number of Distinct values |S| = 4 and |S| == R. So, this is a valid combination.
But, if we choose pairs (a, b, f), the distinct values are:- S = {1, 2, 3, 4, 5} Number of Distinct values |S| = 5 and |S| > R. So, this is not a valid combination.
In this example, there is more valid and invalid combinations. I have to count the valid combination for bigger datasets. Is there any combination formula or Dynamic Programming solution for this problem. An algorithm would be very helpful.
What is the source of the problem?
I thought about this problem. I could not find anything related to this online.
Interesting, $$$n=100, k \geq 50, r \geq k$$$ are constraints that seem quite arbitrary for something that you just thought of.
I'm pretty sure that, unless there are some additional constraints that aren't mentioned in the blog, you can count the number of perfect matchings in a bipartite graph(which isn't possible in polynomial time unless $$$P=NP$$$) by solving this problem by choosing $$$r=2k$$$ and thinking of pairs as edges.
Additional constraints are: x < y for every pairs. x and y are less than equal to 100.
Is it actually a NP problem?
If there are no constraints that prevent you from using the solution to this problem to count the number of perfect matchings in a bipartite graph(from what I can see there aren't any), then it's impossible to solve this problem in polynomial time unless P=NP.
Thank you so much. I needed to be sure if it is a NP problem.
I will let you know, if I can come up with some good constraints.