Search for all possible “lists” of possible pairs in Matlab

Question

I have been thinking about the problem in the last few days, but since I am new to MATLAB, I have no idea how to solve it. Here is the background. Suppose you have a symmetric matrix N×N, where each element has either 0, or 1, and N = (1,2,...,n).

For instance:

A =

    0     1     1     0

    1     0     0     1

    1     0     0     0

    0     1     0     0

If A(i,j) == 1, then it is possible to form a pair (i,j), and if A(i,j)==0, then it is impossible to form a pair (i,j). For example, it (1,2)is a possible pair, because A(1,2)==A(2,1)==1, but is (3,4)NOT a possible pair like A(3,4)==A(4,3)==0.

Here is the problem. Suppose a member of a set Ncan only be for a pair with no more than one other element in the set N(i.e., if 1 forms a pair with 2, then 1 cannot form a pair with 3). How can I find all possible “lists” of possible pairs? In the above example, one “list” will consist of only a pair (1,2). If this pair is formed, then it is impossible to form other pairs. Other "list" will be: ((1,3),(2,4)). I searched the forum and found that the last “list” is the maximum match that can be found, for example, using a two-way approach to the graph. However, I’m not only interested in finding the maximum match; I am interested to find ALL possible “lists” of possible pairs. Another example:

A =

    0     1     1     1

    1     0     0     1

    1     0     0     0

    1     1     0     0

There are three possible lists in this example:

   (1,2)
   ((1,3),(2,4))
   (1,4)

, , , . , . !

Answer 1

.

%// Given data, A
A =[ 0 1 1 1;
    1 0 0 1;
    1 0 0 0;
    1 1 0 0];

%%// The lists  will be stored in 'out' as a cell array and can be accessed as out{1}, out{2}, etc.
out = cell(size(A,1)-1,1);

%%// Code that detects the lists using "selective" diagonals
for k = 1:size(A,1)-1
    [x,y] = find(triu(A,k).*(~triu(ones(size(A)),k+1)));
    out(k) = {[x y]};
end
out(cellfun('isempty',out))=[]; %%// Remove empty lists

%%// Verification - Print out the lists
for k = 1:numel(out)
    disp(out{k})
end

 1     2

 1     3
 2     4

 1     4

1

, , , . "" , , , , 10.

%// Given data, A
A = [0 1 1 1; 1 0 1 1; 1 1 0 1; 1 1 1 0]

%%// Get all pairwise combinations starting with 1
all_combs = sortrows(perms(1:size(A,1)));
all_combs = all_combs(all_combs(:,1)==1,:);

%%// Get the "valid" indices
all_combs_diff = diff(all_combs,1,2);
valid_ind_mat = all_combs(all(all_combs_diff(:,1:2:end)>0,2),:);
valid_ind_mat = valid_ind_mat(all(diff(valid_ind_mat(:,1:2:end),1,2)>0,2),:);

%%// Map the ones of A onto the valid indices to get the lists in a matrix and then cell array
out_cell = mat2cell(valid_ind_mat,repmat(1,[1 size(valid_ind_mat,1)]),repmat(2,[1 size(valid_ind_mat,2)/2]));
A_masked = A(sub2ind(size(A),valid_ind_mat(:,1:2:end),valid_ind_mat(:,2:2:end)));
out_cell(~A_masked)={[]};

%%// Remove empty lists
out_cell(all(cellfun('isempty',out_cell),2),:)=[];

%%// Verification - Print out the lists
disp('Lists =');
for k1 = 1:size(out_cell,1)
    disp(strcat('  List',num2str(k1),':'));
    for k2 = 1:size(out_cell,2)
        if ~isempty(out_cell{k1,k2})
            disp(out_cell{k1,k2})
        end
    end
end

A =

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

Lists =
  List1:
     1     2

     3     4

  List2:
     1     3

     2     4

  List3:
     1     4

     2     3

Answer 2

, , :

%// Set top half to 0, and find indices of all remaining 1's
A(triu(A)==1) = 0;
[ii,jj] = find(A);

%// Put these in a matrix for further processing
P = [ii jj];

%// Sort indices into 'lists' of the kind you defined 
X = repmat({}, size(P,1),1);
for ii = 1:size(P,1)-1
    X{ii}{1} = P(ii,:);
    for jj = ii+1:size(P,1)
        if ~any(ismember(P(ii,:), P(jj,:)))
            X{ii}{end+1} = P(jj,:); end
    end
end