Count number of K combinations from N pairs of elements. When number of distinct value is R.

Revision en1, by Masab, 2021-05-15 13:33:40

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.

Tags #combinatorics, #algorithms, #graph theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Masab 2021-05-15 13:33:40 1202 Initial revision (published)