MATLAB: All combinations of two elements from a 3 by 7 matrix without repeating from the same column

matrix combinations

Hello,
I'd like to create all possible combinations of two elements from a 3 by 7 matrix without repeating elements from the same column. For example if I had a martix
A = [1 2 3 4 5 6 7; 8 9 10 11 12 13 14; 16 17 18 19 20 21 22]
then out = [1 2], [1 9], [1 17], [1 3], [1 10] … are good, but combinations [1 8], [1 16], [2 9] are bad because they're from the same column. And how can I generalise this for any n combinations.
Thanks!

Best Answer

If I presume that you only said you want a constraint on combinations from the same column, since you used that word more often, then there are several ways you might proceed.
The simple answer is to take all possible combinations of 2 elements (without replacement) from the entire array, then toss all cases where the elements came from the same column. This extends simply (in theory) to combinations or more elements. I'd call this a rejection scheme, where you start with the set of all possibilities, then toss those that fail your constraint.
For samples of size 2, that requires generating only 210 combinations.
nchoosek(21,2)
ans =
   210
In the end, it looks like you will have
3^2*nchoosek(7,2)
ans =
   189
possible combinations, so the constraint is not that significant.
You might generate the 210 possible combinations themselves as simply:
C2 = nchoosek(A(:),2);
Then just compute all combinations of two elements from the SAME column as the set of combinations you would exclude. A simple use of setdiff, with the 'rows' option to exclude the samples you don't want will now work.
Extending the latter part to exclude combinations of size n>2 and n<=7 will take a little thought. But I'm not here to write code for you. That would be your job. And really, I'm not advocating a rejection scheme, since it does not extend as nicely to combinations of larger order.
As well, a rejection scheme will grow in size quickly if your real problem is larger than the 3x7 array you initially stated. And people always seem to give a small example, and then assume the answer would be identical if they had a problem 1000 times as large, and that the person answering them would know their real problem was much bigger.
Anyway, rejection schemes might become problematic for larger arrays, or for problems where you want to sample all combinations of order larger than 2.
So while a rejection scheme is often the most obvious, an alternative is to go constructive. Just pick all combinations of two columns. There are
nchoosek(7,2)
ans =
    21
such choices. Then pick all combinations from each pair of columns. A simple scheme would have you just use a loop, over this set of columns:
nchoosek(1:7,2)
ans =
   1     2
   1     3
   1     4
   1     5
   1     6
   1     7
   2     3
   2     4
   2     5
   2     6
   2     7
   3     4
   3     5
   3     6
   3     7
   4     5
   4     6
   4     7
   5     6
   5     7
   6     7
This scheme also extends trivially to combinations of larger order.
How might you simply generate all combinations from two fixed columns? ndgrid will help there. Thus...
[C1,C2] = ndgrid(1:3,1:3);
[C1(:),C2(:)]
ans =
   1     1
   2     1
   3     1
   1     2
   2     2
   3     2
   1     3
   2     3
   3     3
Thus all combinations of 2 elements from two columns, each column of length 3.
Just make sure that you don't grow the array of all combinations in memory. Preallocate it in advance, since you know what the final size will be.
If you write the above code CAREFULLY, it can actually be quite efficient, given the set of combinations you would generate. I see that at most, the final set will be of maximum size 5103 combinations, so the above constructive scheme will be both easy to write and not time consuming at all.
A good thing is that the simple code I describe above will grow in time complexity not too badly if your real problem is larger. Of course, make things too big, and all code becomes nasty and inefficient.
Could you build the set of all such combinations in a vectorized way? Well, yes, you can do so. Is it worth the effort? Your choice, since I won't write it for you, and given the existence of a fairly efficient scheme that uses a loop, why bother? Don't pre-optimize code.
Related Question