Masab's blog

Count number of K combinations from N pairs of elements. When number of distinct value is R.
By Masab, history, 3 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the source of the problem?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    I thought about this problem. I could not find anything related to this online.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Additional constraints are: x < y for every pairs. x and y are less than equal to 100.

        Is it actually a NP problem?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply