# Complex (I think) combination problem?

2 次查看（过去 30 天）

显示 更早的评论

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 个评论

James Tursa
2021-2-8

### 回答（1 个）

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.

### 另请参阅

### 类别

### Community Treasure Hunt

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

Start Hunting!