- #1
grigor
- 4
- 0
Here is the problem I have faced recently that I cannot deal with yet and I need some help:
Given is the
- list of elements (numbered): e.g. [1,2,3,4,6,7,8]
- the count and size of groups, which can be used to cover the given set of numbers, e.g. groups with group size 2.
- I need to find the number of combinations of elements of given length, which can be covered by any placement of element groups
for example,
* if combination_length = 1, all possible combinations are covered: 1, 2, 3, 4, 5, 6, 7, 8 -> combs_count_covered = 8 (out of 28 possible)
* if combination_length = 2, the following combinations are covered: 12, 13, 14, 15, 16, 17, 18, 23, 24, 25, 26, 27, 28, 34, 35, 36, 37, 38, 45, 46, 47, 48, 56, 57, 58, 67, 68, 78 -> combs_count_covered = 28 (out of 28 possible)
* if combination_length = 3, the following combinations are covered: 123, 124, 125, 126, 127, 128, 134, 135, 136, 137, 138, ... -> combs_count_covered = 36 (out of 56 possible), one of the uncovered combinations is e.g., 147, which is not possible to cover with 2 groups, but possible with 3 groups of 2 elements, placed e.g. this way: 12-45-67
* if combination_length = 4, the following combinations are covered: 1234, 1245, 1256, 1267, ... -> combs_count_covered = 15 (out of 70 possible), one of the uncovered combinations is e.g., 1235, which is not possible to cover with 2 groups, but possible with 3 groups of 2 elements, placed e.g. this way: 12-34-56
* if combination_length = 5, coverage with 2 groups is not possible any more.
Of course, the most preferable option will be to get a universal formula, which will receive these parameters and return the number of combinations covered with this configuration, but any ideas are appreciated how to approach the problem.
In case of group_size = 1, group_count = n and group_size = n, group_count = 1, I have got the corresponding formulas, but in general case group_size = k, group_count = n I couldn't find yet such formula.
Given is the
- list of elements (numbered): e.g. [1,2,3,4,6,7,8]
- the count and size of groups, which can be used to cover the given set of numbers, e.g. groups with group size 2.
- I need to find the number of combinations of elements of given length, which can be covered by any placement of element groups
for example,
* if combination_length = 1, all possible combinations are covered: 1, 2, 3, 4, 5, 6, 7, 8 -> combs_count_covered = 8 (out of 28 possible)
* if combination_length = 2, the following combinations are covered: 12, 13, 14, 15, 16, 17, 18, 23, 24, 25, 26, 27, 28, 34, 35, 36, 37, 38, 45, 46, 47, 48, 56, 57, 58, 67, 68, 78 -> combs_count_covered = 28 (out of 28 possible)
* if combination_length = 3, the following combinations are covered: 123, 124, 125, 126, 127, 128, 134, 135, 136, 137, 138, ... -> combs_count_covered = 36 (out of 56 possible), one of the uncovered combinations is e.g., 147, which is not possible to cover with 2 groups, but possible with 3 groups of 2 elements, placed e.g. this way: 12-45-67
* if combination_length = 4, the following combinations are covered: 1234, 1245, 1256, 1267, ... -> combs_count_covered = 15 (out of 70 possible), one of the uncovered combinations is e.g., 1235, which is not possible to cover with 2 groups, but possible with 3 groups of 2 elements, placed e.g. this way: 12-34-56
* if combination_length = 5, coverage with 2 groups is not possible any more.
Of course, the most preferable option will be to get a universal formula, which will receive these parameters and return the number of combinations covered with this configuration, but any ideas are appreciated how to approach the problem.
In case of group_size = 1, group_count = n and group_size = n, group_count = 1, I have got the corresponding formulas, but in general case group_size = k, group_count = n I couldn't find yet such formula.