how to get the intersection of many different length cell vectors in matlab

Question

I have n different length cell vectors, call it c{i}, i=1,2,...,n.

I wanna know if there any c{j} is the subset of c{i}, for example:

c{1}=[1 2 3 4 5 6]; c{2}=[1 3 5 7];c{3}=[2 4 6 8];
c{4}=[1 4 6];c{5}=[3 7];

then I hope I can find that c{4} is subset of c{1}, c{5} is subset of c{2}.

I used two for loops with intersect function can process it, but I hope I can use at most one loop to process it, is there any way can achieve it?

Answer 1

Building on the other answers, you can also use ismember:

sets = {[1 2 3 4 5 6], [1 3 5 7], [2 4 6 8], [1 4 6], [3 7]};

N = numel(sets);          % number of sets
idx = nchoosek(1:N,2);    % indices of combinations
subsets = false(N,N);
for i = 1:size(idx,1)
    a = idx(i,1); b = idx(i,2);

    % check that set A is a subset of B, and the other way around as well
    subsets(a,b) = all(ismember(sets{a},sets{b}));
    subsets(b,a) = all(ismember(sets{b},sets{a}));
end

We get a logical matrix:

>> subsets
subsets =
     0     0     0     0     0
     0     0     0     0     0
     0     0     0     0     0
     1     0     0     0     0
     0     1     0     0     0

where non-zeros indicate subset relationship:

>> [i,j] = find(subsets)
i =
     4
     5
j =
     1
     2

i.e c{4} is a subset of c{1}, and c{5} is a subset of c{2}

Note: it is obvious that any set is a subset of itself, so the diagonals of subsets matrix should also be made 1. You could add that if you want using:

subsets(1:N+1:end) = true;

Answer 2

Here's a option using nchoosek – like cellfun it's also a loop in disguise of course:

c{1} = [1 2 3 4 5 6];
c{2} = [1 3 5 7];
c{3} = [2 4 6 8];
c{4} = [1 4 6];
c{5} = [3 7];
combs = nchoosek(1:numel(c),2);
subC = cell(size(combs,1),1);
for i = 1:size(combs,1)
    subC{i} = intersect(c{combs(i,:)});
end

which results in the cell array

subC = 

    [1x3 double]
    [1x3 double]
    [1x3 double]
    [         3]
    [1x0 double]
    [         1]
    [1x2 double]
    [1x2 double]
    [1x0 double]
    [1x0 double]

Each cell in subC corresponds to intersection of the cells indices in combs (a matrix form could easily be built within the loop if that is preferred).

EDIT: If you simply want to know if one vector is a subset of another then you can either use subC and combs from above to determine this or calculate it directly

combs = nchoosek(1:numel(c),2);
isSubC = logical(eye(numel(c)));
for i = 1:size(combs,1)
    subC = intersect(c{combs(i,:)});
    isSubC(combs(i,1),combs(i,2)) = isequal(subC,c{combs(i,2)});
    isSubC(combs(i,2),combs(i,1)) = isequal(subC,c{combs(i,1)});
end

where isSubC(i,j) specifies if c{j} is a subset of c{i}.

Answer 3

You can by using cellfun, but as stated here, it is not a good idea.

For doing so, with one loop:

c{1}=[1 2 3 4 5 6]; c{2}=[1 3 5 7];c{3}=[2 4 6 8];
c{4}=[1 4 6];c{5}=[3 7];
cSize = numel( c);
isect=cell(1,cSize)
for k=1:cSize
  isect{k}=cellfun(@(in) intersect(in,c{k}),c,'UniformOutput',false);
end

This procedure may be repeated to eliminate the other for:

c{1}=[1 2 3 4 5 6]; c{2}=[1 3 5 7];c{3}=[2 4 6 8];
c{4}=[1 4 6];c{5}=[3 7];
isect=cellfun(@(in) cellfun(@(in2) intersect(in,in2),c,'UniformOutput',false),c,'UniformOutput',false);

isect{i}{j} is the intersection from c{i} to {j}

Note: cellfun will do the loop internally over the cell value, so in fact, you are not removing the loops.

---

Although this was not the initial question, finding the subsets:

c{1}=[1 2 3 4 5 6]; c{2}=[1 3 5 7];c{3}=[2 4 6 8];
c{4}=[1 4 6];c{5}=[3 7];c{6}=[];
isSubset=cell2mat(cellfun(@(in) cellfun(@(in2) isequal(intersect(in,in2),in)|isempty(in),c),c,'UniformOutput',false)');

Results:

isSubset =

 1     0     0     0     0     0
 0     1     0     0     0     0
 0     0     1     0     0     0
 1     0     0     1     0     0
 0     1     0     0     1     0
 1     1     1     1     1     1

Which returns a boolean if k is a subset of m by doing isSubset(k,m).