Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Combinations of entire rows from several matrices

Subject: Combinations of entire rows from several matrices

From: Matt

Date: 23 Oct, 2010 04:30:07

Message: 1 of 8

Hi all:

Here's an example of what I'm trying to do. Take two matrices

S1 = [ 1 0; 0 1 ]
S2 = [ 1 2 3; 4 5 6; 7 8 9; 10 11 12 ]

with dimensions 2x2 and 4x3, respectively. I want to find all combinations of row vectors from S1 and S2, thus producing a matrix

C =
[ 1 0 1 2 3;
1 0 4 5 6;
1 0 7 8 9;
1 0 10 11 12;
0 1 1 2 3;
0 1 4 5 6;
0 1 7 8 9;
0 1 10 11 12]

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.

Thanks,
Matt

Subject: Combinations of entire rows from several matrices

From: ImageAnalyst

Date: 23 Oct, 2010 04:38:07

Message: 2 of 8

Matt:
Here's one pretty straightforward easy to understand intuitive way,
although I'm sure someone will come up with a compact, cryptic, hard
to understand one-liner shortly:

S1 = [ 1 0; 0 1 ]
S2 = [ 1 2 3; 4 5 6; 7 8 9; 10 11 12 ]

[rows1 cols1] = size(S1);
[rows2 cols2] = size(S2);
counter = 1;
C = zeros(rows1*rows2, (cols1+cols2));
for k1 = 1:rows1
    for k2 = 1:rows2
        C(counter, :) = [S1(k1, :) S2(k2, :)];
        counter = counter + 1
    end
end
C % Display in command window.

Subject: Combinations of entire rows from several matrices

From: Matt

Date: 23 Oct, 2010 05:36:04

Message: 3 of 8

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 example---and I certainly want to avoid one hundred manually written for loops!

P.S. Your comment about one line solutions gave me a good laugh. I only use Matlab occasionally so super-optimized densely vectorized code can take me forever to read!

Subject: Combinations of entire rows from several matrices

From: Roger Stafford

Date: 23 Oct, 2010 05:59:04

Message: 4 of 8

"Matt " <economatt@gmail.com> wrote in message <i9tocf$60b$1@fred.mathworks.com>...
> Hi all:
>
> Here's an example of what I'm trying to do. Take two matrices
>
> S1 = [ 1 0; 0 1 ]
> S2 = [ 1 2 3; 4 5 6; 7 8 9; 10 11 12 ]
>
> with dimensions 2x2 and 4x3, respectively. I want to find all combinations of row vectors from S1 and S2, thus producing a matrix
>
> C =
> [ 1 0 1 2 3;
> 1 0 4 5 6;
> 1 0 7 8 9;
> 1 0 10 11 12;
> 0 1 1 2 3;
> 0 1 4 5 6;
> 0 1 7 8 9;
> 0 1 10 11 12]
>
> 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.
>
> Thanks,
> Matt
- - - - - - - -
  For just the two arrays, S1 and S2, do:

[p2,p1] = ndgrid(1:size(S2,1),1:size(S1,1));
C = [S1(p1,:),S2(p2,:)];

For N arrays the generalization of this is obvious, since 'ndgrid' can take many such arguments and a like number of outputs.

  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.

Roger Stafford

Subject: Combinations of entire rows from several matrices

From: Roger Stafford

Date: 23 Oct, 2010 06:11:04

Message: 5 of 8

"Matt " <economatt@gmail.com> wrote in message <i9ts84$9rp$1@fred.mathworks.com>...
> 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 example---and I certainly want to avoid one hundred manually written for loops!
>
> P.S. Your comment about one line solutions gave me a good laugh. I only use Matlab occasionally so super-optimized densely vectorized code can take me forever to read!
- - - - - - - -
  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.

Roger Stafford

Subject: Combinations of entire rows from several matrices

From: Matt

Date: 23 Oct, 2010 06:43:04

Message: 6 of 8

Roger,

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.

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.

Matt

Subject: Combinations of entire rows from several matrices

From: Bruno Luong

Date: 23 Oct, 2010 09:59:04

Message: 7 of 8

"Matt " <economatt@gmail.com> wrote in message <i9u05o$d5e$1@fred.mathworks.com>...

>
> 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?

If you still think storing is possible then you still have no idea how big 2^100 is.

Bruno

Subject: Combinations of entire rows from several matrices

From: Roger Stafford

Date: 23 Oct, 2010 19:13:05

Message: 8 of 8

"Matt " <economatt@gmail.com> wrote in message <i9u05o$d5e$1@fred.mathworks.com>...
> Roger,
>
> 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.
>
> 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.
>
> Matt
- - - - - - - - - - -
  It is easy enough to get random samples of combinations, even for large numbers of arrays.

 t = [size(S1,1),size(S2,1),size(S3,1),...,size(SN,1)];
 p = ceil(bsxfun(@times,t,rand(M,N)));
 C = [S1(p(:,1),:),S2(p(:,2),:),S3(p(:,3),:),...,SN(p(:,N),:)];

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.

  If even this size C proved to be too large for your memory, you could use a for-loop to produce the above random rows one at a time and store in C only those rows which meet the criterion.

  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.

 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?

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us