http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606
MATLAB Central Newsreader  Combinations of entire rows from several matrices
Feed for thread: Combinations of entire rows from several matrices
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Sat, 23 Oct 2010 04:30:07 +0000
Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790051
Matt
Hi all:<br>
<br>
Here's an example of what I'm trying to do. Take two matrices<br>
<br>
S1 = [ 1 0; 0 1 ]<br>
S2 = [ 1 2 3; 4 5 6; 7 8 9; 10 11 12 ]<br>
<br>
with dimensions 2x2 and 4x3, respectively. I want to find all combinations of row vectors from S1 and S2, thus producing a matrix<br>
<br>
C = <br>
[ 1 0 1 2 3;<br>
1 0 4 5 6;<br>
1 0 7 8 9;<br>
1 0 10 11 12;<br>
0 1 1 2 3;<br>
0 1 4 5 6;<br>
0 1 7 8 9;<br>
0 1 10 11 12]<br>
<br>
In general, I will have N matrices S1 ... SN, where the number and dimension of these matrices are parameters to be set by the user. I am storing these in a cell array because their dimensions are arbitrary and unrelated to each other. Any thoughts or tips on how to find this matrix C from my matrices S1 ... SN? Most of the methods I know or have read about involve taking combinations of elements in matrices, not combinations of entire rows. The only solutions I've come up with so far are far too clunky.<br>
<br>
Thanks,<br>
Matt

Sat, 23 Oct 2010 04:38:07 +0000
Re: Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790053
ImageAnalyst
Matt:<br>
Here's one pretty straightforward easy to understand intuitive way,<br>
although I'm sure someone will come up with a compact, cryptic, hard<br>
to understand oneliner shortly:<br>
<br>
S1 = [ 1 0; 0 1 ]<br>
S2 = [ 1 2 3; 4 5 6; 7 8 9; 10 11 12 ]<br>
<br>
[rows1 cols1] = size(S1);<br>
[rows2 cols2] = size(S2);<br>
counter = 1;<br>
C = zeros(rows1*rows2, (cols1+cols2));<br>
for k1 = 1:rows1<br>
for k2 = 1:rows2<br>
C(counter, :) = [S1(k1, :) S2(k2, :)];<br>
counter = counter + 1<br>
end<br>
end<br>
C % Display in command window.

Sat, 23 Oct 2010 05:36:04 +0000
Re: Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790058
Matt
Thank you for the quick reply! Your solution works for 2 matrices, but what about more than 2? Ultimately I have to figure out how to do this for about 100 matrices, for exampleand I certainly want to avoid one hundred manually written for loops!<br>
<br>
P.S. Your comment about one line solutions gave me a good laugh. I only use Matlab occasionally so superoptimized densely vectorized code can take me forever to read!

Sat, 23 Oct 2010 05:59:04 +0000
Re: Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790061
Roger Stafford
"Matt " <economatt@gmail.com> wrote in message <i9tocf$60b$1@fred.mathworks.com>...<br>
> Hi all:<br>
> <br>
> Here's an example of what I'm trying to do. Take two matrices<br>
> <br>
> S1 = [ 1 0; 0 1 ]<br>
> S2 = [ 1 2 3; 4 5 6; 7 8 9; 10 11 12 ]<br>
> <br>
> with dimensions 2x2 and 4x3, respectively. I want to find all combinations of row vectors from S1 and S2, thus producing a matrix<br>
> <br>
> C = <br>
> [ 1 0 1 2 3;<br>
> 1 0 4 5 6;<br>
> 1 0 7 8 9;<br>
> 1 0 10 11 12;<br>
> 0 1 1 2 3;<br>
> 0 1 4 5 6;<br>
> 0 1 7 8 9;<br>
> 0 1 10 11 12]<br>
> <br>
> In general, I will have N matrices S1 ... SN, where the number and dimension of these matrices are parameters to be set by the user. I am storing these in a cell array because their dimensions are arbitrary and unrelated to each other. Any thoughts or tips on how to find this matrix C from my matrices S1 ... SN? Most of the methods I know or have read about involve taking combinations of elements in matrices, not combinations of entire rows. The only solutions I've come up with so far are far too clunky.<br>
> <br>
> Thanks,<br>
> Matt<br>
       <br>
For just the two arrays, S1 and S2, do:<br>
<br>
[p2,p1] = ndgrid(1:size(S2,1),1:size(S1,1));<br>
C = [S1(p1,:),S2(p2,:)];<br>
<br>
For N arrays the generalization of this is obvious, since 'ndgrid' can take many such arguments and a like number of outputs.<br>
<br>
Any scheme that gets all possible combinations of single elements, one from each of N groups can be used on indices in this way to get all possible combinations of rows, one from each array.<br>
<br>
Roger Stafford

Sat, 23 Oct 2010 06:11:04 +0000
Re: Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790062
Roger Stafford
"Matt " <economatt@gmail.com> wrote in message <i9ts84$9rp$1@fred.mathworks.com>...<br>
> Thank you for the quick reply! Your solution works for 2 matrices, but what about more than 2? Ultimately I have to figure out how to do this for about 100 matrices, for exampleand I certainly want to avoid one hundred manually written for loops!<br>
> <br>
> P.S. Your comment about one line solutions gave me a good laugh. I only use Matlab occasionally so superoptimized densely vectorized code can take me forever to read!<br>
       <br>
Matt, I think you need to pause to consider what would be involved with your N equal to 100. Even if each of these one hundred arrays possessed only two rows, finding all possible combinations of a hundred rows, one from each array, would amount to 2^100 combinations! That's a number with 31 digits in it, and certainly more than any computer's memory can possibly hold by a very large margin. You had better lower your sights on what you wish to achieve in the way of larger N's.<br>
<br>
Roger Stafford

Sat, 23 Oct 2010 06:43:04 +0000
Re: Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790063
Matt
Roger,<br>
<br>
Thanks for the help. Yeah, 2^100 is quite a large number indeed. Actually, in my application I only care about a very small subset of matrix C of combinations, those combinations whose distance to another fixed vector is very small.<br>
<br>
So perhaps I can still save everything even when N is relatively large by cycling through the possibilities and only storing those combinations of interest? It's not necessary that I ever know the entire matrix C at once. Probably the loop (again, through >=2^100 values....!) will take way too long though, I don't know. If that is not feasible then it may be possible to take a small random subsample of combinations and then loop through those, although this would require extra work to figure out how decent an approximation this is. Anyway, back to the drawing board. Thanks for the tips above.<br>
<br>
Matt

Sat, 23 Oct 2010 09:59:04 +0000
Re: Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790072
Bruno Luong
"Matt " <economatt@gmail.com> wrote in message <i9u05o$d5e$1@fred.mathworks.com>...<br>
<br>
> <br>
> So perhaps I can still save everything even when N is relatively large by cycling through the possibilities and only storing those combinations of interest?<br>
<br>
If you still think storing is possible then you still have no idea how big 2^100 is.<br>
<br>
Bruno

Sat, 23 Oct 2010 19:13:05 +0000
Re: Combinations of entire rows from several matrices
http://www.mathworks.com/matlabcentral/newsreader/view_thread/294606#790120
Roger Stafford
"Matt " <economatt@gmail.com> wrote in message <i9u05o$d5e$1@fred.mathworks.com>...<br>
> Roger,<br>
> <br>
> Thanks for the help. Yeah, 2^100 is quite a large number indeed. Actually, in my application I only care about a very small subset of matrix C of combinations, those combinations whose distance to another fixed vector is very small.<br>
> <br>
> So perhaps I can still save everything even when N is relatively large by cycling through the possibilities and only storing those combinations of interest? It's not necessary that I ever know the entire matrix C at once. Probably the loop (again, through >=2^100 values....!) will take way too long though, I don't know. If that is not feasible then it may be possible to take a small random subsample of combinations and then loop through those, although this would require extra work to figure out how decent an approximation this is. Anyway, back to the drawing board. Thanks for the tips above.<br>
> <br>
> Matt<br>
          <br>
It is easy enough to get random samples of combinations, even for large numbers of arrays. <br>
<br>
t = [size(S1,1),size(S2,1),size(S3,1),...,size(SN,1)];<br>
p = ceil(bsxfun(@times,t,rand(M,N)));<br>
C = [S1(p(:,1),:),S2(p(:,2),:),S3(p(:,3),:),...,SN(p(:,N),:)];<br>
<br>
This would give you M samples of combinations of the rows of N arrays. The array C will have M rows and each row will have a number of elements equal to the sum of the row sizes of the S arrays. You could then select out of these the subset of C rows that satisfy your criterion.<br>
<br>
If even this size C proved to be too large for your memory, you could use a forloop to produce the above random rows one at a time and store in C only those rows which meet the criterion.<br>
<br>
However, all this is a far cry from obtaining all possible combinations. You are entirely correct when you say that going "through >=2^100 values will take way too long". It is something that can be estimated fairly well, and as Bruno (and I) assert, the number 2^100 is a truly enormous number. Even on the fastest computers known to man, the universe will undoubtedly have suffered a heat (entropy) death before the computer could complete the task.<br>
<br>
One thing I don't understand, Matt. You say you are only interested in "those combinations whose distance to another fixed vector is very small." If your notion of distance is the square root of the sum of the squares of differences in the elements, it seems to me that you are wasting time and space dealing with whole rows from the S arrays. For each row of an S array there is a single sum of squares of its differences with the corresponding elements of this fixed vector which could easily be precomputed. Instead of randomly selecting rows of S arrays you can just randomly select among these sums of squared differences. Why fool around with randomly selecting entire rows at all?<br>
<br>
Roger Stafford