Cartesian product of row-indices in Matlab

Question

I have a binary matrix A of dimension mxn with m>n in Matlab. I want to construct a matrix B of dimension cxn listing row wise each element of the Cartesian product of the row indices of the ones contained in A. To be more clear consider the following example.

Example:

  %m=4;
  %n=3;

  A=[1 0 1;
     0 0 1;
     1 1 0;
     0 0 1];

  %column 1: "1" are at rows {1,3}
  %column 2: "1" are at row {3}
  %column 3: "1" are at rows {1,2,4}

  %Hence, the Cartesian product {1,3}x{3}x{1,2,4} is 
  %{(1,3,1),(1,3,2),(1,3,4),(3,3,1),(3,3,2),(3,3,4)} 

  %I construct B by disposing row-wise each 3-tuple in the Cartesian product

  %c=6

 B=[1 3 1;
    1 3 2;
    1 3 4;
    3 3 1;
    3 3 2;
    3 3 4];

Noel Segura Meraz · Accepted Answer · 2016-07-28T12:47:34.763

4

You can get the cartesian product with the combvec command, for your example:

A=[1 0 1;...
   0 0 1;...
   1 1 0;...
   0 0 1];

[x y]=find(A);

B=combvec(x(y==1).',x(y==2).',x(y==3).').';

% B =
%    1   3   1
%    3   3   1
%    1   3   2
%    3   3   2
%    1   3   4
%    3   3   4

You can expand this to an unknown number of columns by using the associative property of the product.

[x y]=find(A);

u_y=unique(y);

B=x(y==u_y(1)).';

for i=2:length(u_y)
    B=combvec(B, x(y==u_y(i)).');
end

B=B.';

edited Jul 28 '16 at 12:47

answered Jul 28 '16 at 12:25

Noel Segura Meraz

2,265
1
12
17

1

Warning. `combvec` belongs to the Neural Networks toolbox. – rayryeng Jul 29 '16 at 04:54

obchardon · Answer 2 · 2016-07-28T12:54:55.943

3

One solution (without toolbox):

A=  [1 0 1;
     0 0 1;
     1 1 0;
     0 0 1];



[ii,jj] = find(A)

kk = unique(jj); 

for i = 1:length(kk)
    v{i} = ii(jj==kk(i));
end

t=cell(1,length(kk));
[t{:}]= ndgrid(v{:});

product = []
for i = 1:length(kk)
    product = [product,t{i}(:)];
end

edited Jul 28 '16 at 12:54

answered Jul 28 '16 at 12:27

obchardon

10,614
1
17
33

Interesting, I see we have similar codes besides minor differences in indexing and creating matrices. – edwinksl Jul 28 '16 at 13:10

score 3 · Answer 3 · edited May 23 '17 at 12:32

You can use use accumarray to obtain vectors with the row indices of nonzero elements for each column. This works for an arbitrary number of columns:

[ii, jj] = find(A);
vectors = accumarray(jj, ii, [], @(x){sort(x.')});

Then apply this answer to efficiently compute the Cartesian product of those vectors:

n = numel(vectors);
B = cell(1,n);
[B{end:-1:1}] = ndgrid(vectors{end:-1:1});
B = cat(n+1, B{:});
B = reshape(B,[],n);

In your example, this gives

B =
     1     3     1
     1     3     2
     1     3     4
     3     3     1
     3     3     2
     3     3     4

edwinksl · Answer 4 · 2016-07-28T13:12:46.980

In short, I would use find to generate the indices needed for the Cartesian product and then use ndgrid to perform the Cartesian product of these indices. The code to do so is:

clear
close all
clc

A = [1 0 1;
     0 0 1;
     1 1 0;
     0 0 1];

[row,col] = find(A);
[~,ia,~] = unique(col);
n_cols = size(A,2);
indices = cell(n_cols,1);

for ii = 1:n_cols-1
  indices{ii} = row(ia(ii):ia(ii+1)-1);
end
indices{end} = row(ia(end):end);

cp_temp = cell(n_cols,1);
[cp_temp{:}] = ndgrid(indices{:});

cp = NaN(numel(cp_temp{1}),n_cols);
for ii = 1:n_cols
  cp(:,ii) = cp_temp{ii}(:);
end
cp = sortrows(cp);
cp

Cartesian product of row-indices in Matlab

4 Answers4

Linked