Complex (I think) combination problem?

1 次查看（过去 30 天）
Mark Lepage
Mark Lepage 2021-2-8
评论： Mark Lepage 2021-2-9
Hello everyone,
I'm wondering how I could go about solving this combination problem.
I have 5 groups, that I need to select from to create another group.
For example:
A = [1,2,3,4,5]
B = [3,4,5,6,7,8]
C = [7,8,9,10,11,12]
D = [13,14,15,16,17]
E = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
From each group, I need select a certain number from each group, and I don't want any duplicates.
For example:
A = [1,2,3] % need 3 from group A
B = [4,5,6] % need 3 from group B
C = [7,8,9] % need 3 from group C
D = [13,14,15,16] % need 4 from group D
E = [10,11] % need 2 from group E
How I initially solved this problem was to calculate the combinations from each group using for example:
combinations_A = nchoosek(A,3) %combinations of group A, choosing 3 from A
Then I simply looped through every single combination of every group in a nested for loop, i.e.
for ii = 1:size(combinations_A,1)
for jj = 1:size(combinations_B,1)
for kk = 1:size(combinations_C,1)
for ij = 1:size(combinations_D,1)
for jk = 1:size(combinations_E,1)
% do some analysis on this combination
end
end
end
end
end
This however doesn't take into the fact that I can't have the same number in a given selected group. This also balloons the problem. For the total number in my problem, it calculated that there would be over 250,000,000 combintations, and thus I could not even initialize my matrix it was so large.
Anyone have any idea how I could simplify this problem?
  8 个评论
显示 6更早的评论
James Tursa
James Tursa 2021-2-8
Well, how large can the groups be? The viability of any approach will depend on the maximum group sizes.
Mark Lepage
Mark Lepage 2021-2-9
编辑：Mark Lepage 2021-2-9
The groups could range from the min required from each group to the total number available.
So the min would be the total number showed above, with the max being 22.
Keeping in mind that every group could have all the same values (i.e. 1, 2, 3... 21, 22)

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Walter Roberson
Walter Roberson 2021-2-8
Not really simplifying, but more automating:
You could adapt my odometer functions from https://www.mathworks.com/matlabcentral/answers/623358-get-a-combination-of-unique-paths-for-given-pair-of-numbers#comment_1082638 to generate all of the possibilities systematically. The current functions do not accomedate "N unique out of this group", but changing that should not require a major redesign.
Those functions do not have any ability to reduce the number of combinations, other than the fact that a minor modification could remove duplicates as soon as they show up, so you do not (for example) end up trying to generate several tens of millions of possibilities each with a duplicate in the first group, only to eliminate those in post processing. So no ability to reduce the number of valid combinations, and no ability to avoid generating temporary combinations with one invalid situation -- but the technique can avoid generating temporary combinations with two simultaneous invalid situations, which prunes out a lot.
What the functions are good for is generating the possibilities systematically, incrementally, using only a small amount of state memory, fetching just the next possibility each time. Non-vectorized brute force.... and thus good for cases where the full set of values would take too much memory.
  6 个评论
显示 4更早的评论
Mark Lepage
Mark Lepage 2021-2-9
I'm thinking I could just create temporary pipes as I go down each pipeline.
This is a very elegant solution, which I may look to implement in the future (if the number of groups ever change).
For now, I will use your idea, and attempt implement this odometer method with for loops, where I remove the values from the further nested for loops, to reduce the calculations... much less elegant, but just need a working for solution...
Will report back
Mark Lepage
Mark Lepage 2021-2-9
Again the issue with any sort of method where all combinations are tested is the shear number of combinations generated.
The true value should be less than 816 where as if every single combination is tested, over 250,000,000 are generated...

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by