One/zero Matrix, merge subset of columns

Say I have this matrix of ones and zeros, 10x6:

x= [    0	0	0	1	0	0
        0	1	1	1	1	1
        0	1	1	0	1	1
        0	0	0	0	0	0
        0	0	0	0	0	0
        1	0	0	0	0	0
        0	0	1	1	1	1
        0	0	0	0	0	1
        0	0	0	0	0	1
        0	0	0	0	1	1];

I would like to remove the columns that are a subset of any other column. For instance, column 2 is a subset of column 3 (because all ones in column 2 are in the same rows of column 3). Similarly column 3 is a subset of column 6, then columns 3 should be eliminated. At the end only the columns are not "subset" of other should remain only. So in the example, I should get:

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

The order of te columns is not importan, but the speed.

Any hint will be very much appreciatted. Thanks!

Answer 1

[Jan]

x0 = [  0,	0,	0,	1,	0,	0; ...
	0,	1,	1,	1,	1,	1; ...
	0,	1,	1,	0,	1,	1; ...
	0,	0,	0,	0,	0,	0; ...
	0,	0,	0,	0,	0,	0; ...
	1,	0,	0,	0,	0,	0; ...
	0,	0,	1,	1,	1,	1; ...
	0,	0,	0,	0,	0,	1; ...
	0,	0,	0,	0,	0,	1; ...
	0,	0,	0,	0,	1,	1];

% Save memory:
x = logical(x0);

for Iter = 1:2  % From left to right and right to left
    nCol = size(x, 2);
    del  = false(1, nCol);
    for iCol = 1:nCol
        col = x(:, iCol);
        for jCol = iCol + 1:nCol
            if all(and(col, x(:, jCol)) == col)
                del(iCol) = true;
                break
            end
        end
    end
    x(:, del) = [];
    x         = x(:, end:-1:1);  % Change order
end

Another apporach:

x    = logical(x0);  % Save memory
nCol = size(x, 2);
del  = false(1, nCol);
for iCol = 1:nCol
    if ~del(iCol)
        col = x(:, iCol);
        for jCol = iCol + 1:nCol
            if ~del(jCol)
                both = and(col, x(:, jCol));
                if all(both == x(:, jCol))
                    del(jCol) = true;
                elseif all(both == col)
                    del(iCol) = true;
                    break
                end
            end
        end
    end
end
x(:, del) = [];

Answer 2

[Image Analyst]

Try this. It will give you what you wanted.

x= [    0	0	0	1	0	0
	0	1	1	1	1	1
	0	1	1	0	1	1
	0	0	0	0	0	0
	0	0	0	0	0	0
	1	0	0	0	0	0
	0	0	1	1	1	1
	0	0	0	0	0	1
	0	0	0	0	0	1
	0	0	0	0	1	1];
[rows, columns] = size(x)
% Initialize an array of the columns we may need to delete.
columnsToDelete = false(1, columns);
for col = 1 : columns
	% Get this Column
	thisColumn = x(:, col);
	% Scan the other columns.
	for col2 = col + 1 : columns
		otherColumn = x(:, col2);
		% And them together and see if it's the same as the first column
		anded = thisColumn & otherColumn;
		if all(anded == thisColumn)
			% It's a subset.
			fprintf('Column %d is a subset of column %d.\n', col, col2);
			% Log that col is a subset of some other column.
			columnsToDelete(col) = true;
		end
	end
end
% Now delete those columns that were determined to be 
% a subset of any of the columns to the right in the array.
xOut = x; % First initialize a copy for the output.
% Now delete the columns we need to.
xOut(:, columnsToDelete) = [] % Setting to null removes the column.

You could also just extract the columns you want, so instead of the last few lines, have this:

% Now take a subset of any of the columns in the array
% by taking the inverse of the logical vector.
xOut = x(:, ~columnsToDelete); % Extract the columns we want.

They're just 2 different ways of getting xOut.

[Rub Ron]

Does not work for this x:

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

it gives 4 columns, but it should be only this column (the first column)

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

[Image Analyst]

If you want to compare both before and after the column when looking at other columns, you can just make the obvious modifications to the inner loop to get what you want:

clc;    % Clear the command window.
clear all;
close all;
workspace;  % Make sure the workspace panel is showing.
format short g;
format compact;
fontSize = 15;
fprintf('Beginning to run %s.m ...\n', mfilename);

x= [ 1	0	0	0	0	0
1	0	0	1	1	1
1	0	0	1	1	1
1	0	0	1	1	1
1	0	0	1	1	0
1	0	0	1	1	0
1	0	0	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
0	0	0	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
1	1	1	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
1	0	0	0	0	0
1	0	0	1	1	0
1	0	0	0	0	0];
[rows, columns] = size(x)
% Initialize an array of the columns we may need to delete.
columnsToDelete = false(1, columns);
for col = 1 : columns
	% Get this Column
	thisColumn = x(:, col);
	% Scan the other columns.
	for col2 = 1 : columns
		if col2 == col
			% Skip the column if it's comparing it to itself.
			continue;
		end
		otherColumn = x(:, col2);
		% And them together and see if it's the same as the first column
		anded = thisColumn & otherColumn;
		if all(anded == thisColumn)
			% It's a subset.
			fprintf('Column %d is a subset of column %d.\n', col, col2);
			% Log that col is a subset of some other column.
			columnsToDelete(col) = true;
		end
	end
end
% Now delete those columns that were determined to be 
% a subset of any of the columns to the right in the array.
xOut = x; % First initialize a copy for the output.
% Now delete the columns we need to.
xOut(:, columnsToDelete) = [] % Setting to null removes the column.

fprintf('Done running %s.m ...\n', mfilename);

[Rub Ron]

Now,it does not work with this x:

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

it should give:

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

[Image Analyst]

Well, column 1 was a subset of column 2 so it got deleted.