MATLAB Answers

Complex (I think) combination problem?

1 view (last 30 days)
Mark Lepage
Mark Lepage on 8 Feb 2021
Commented: Mark Lepage on 9 Feb 2021
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 Comments
Mark Lepage
Mark Lepage on 9 Feb 2021
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)

Sign in to comment.

Answers (1)

Walter Roberson
Walter Roberson on 8 Feb 2021
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 Comments
Mark Lepage
Mark Lepage on 9 Feb 2021
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...

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!