How to determine sets with only unique values across the columns of a large logical array?

Given a logical array of size 20524x13500, how could the sets of "wholly unique" columns be determined? Ideally, without resorting to a loop. By "wholly unique", I mean identifying each column that doesn't share any 1 values with other columns.

I.E. If my matrix =

0 0 0 1

0 0 1 1

0 1 1 0

1 1 0 0

1 0 0 0

uniqueIndices = [1, 3];

Note that the example also has [2,4] as a possible solution. How would I select the solution? Given the large size of my logical array, speed is a higher priority but the solution with the lowest valued indices is preferred. If it is relevant, my program tracks which particles are part of a moving grain boundary across 13500 timesteps, so on average it is unlikely to return to previous values. Thank you!

Answer 1

[Fangjun Jiang]

Since it is comparing just two columns,I think you have to use loop. Utilize the logical(),all() and any() function.

matrix =[0     0     0     1
     0     0     1     1
     0     1     1     0
     1     1     0     0
     1     0     0     0];
matrix=logical(matrix);
FindWhollyUniqueColumn(matrix)

ans = 1x2

1 3

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

function index=FindWhollyUniqueColumn(matrix)

for m=1:size(matrix,2)-1
    for n=m+1:size(matrix,2)
        if ~any(all(matrix(:,[m,n]),2))
            index=[m,n];
            return;
        end
    end
end
index=[];
disp('not found');
end

Answer 2

[John D'Errico]

Are you asking for ALL pairs that share no common elements? That will probably require loops. But I would not use a double loop. Just one loop will be sufficient. Compare the first column to all columns that follow. Then compare column 2 to those after it, etc.

A problem is, you DO NOT want to build the list as a dynamic growing thing. That will be terribly inefficient. I might do it like this:

tic,
n = 10000;m = 1000;
A = rand(n,m) < 0.01; % my sample data
pairCell = cell(1,m-1);
for i = 1:m-1
  % This next line requires R2016b or later to work properly
  c = i + find(~any(A(:,i) & A(:,i+1:end),1));
  nc = numel(c);
  if nc > 0
    pairCell{i} = [repmat(i,1,nc);c];
  end
end
% aggregate all pairs into a flat array
pairs = horzcat(pairCell{:});
toc

Elapsed time is 3.256357 seconds.

size(pairs,2)

ans = 184411

That was not too slow. Just a few seconds. With some effort, I could probably make it faster. There were 180000 or so pairs that share no elements in common. A few of them are:

pairs(:,1:10)

ans = 2x10

1 1 1 1 1 1 1 1 1 1 2 4 5 6 7 8 11 13 15 16

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

Can you find pairs that happen early? You might decide to search for the pair with the smallest sum of row plus column index. The first 10 such pairs based on that criterion are:

PCsum = sum(pairs,1);
[PSsumsort,tags] = sort(PCsum,'ascend');
pairs(:,tags(1:10))

ans = 2x10

1 1 2 1 1 2 3 1 1 4 2 4 3 5 6 5 4 7 8 6

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>