matlab - 在 Matlab 中查找所有可能的 “lists” 对

Question

最近几天我一直在思考一个问题，但作为 MATLAB 的初学者，我不知道如何解决它。这是背景。假设您有一个对称的 N×N 矩阵，其中每个元素都是 0 或 1，并且 N = (1,2 ,...,n)。

例如:

A =

    0     1     1     0

    1     0     0     1

    1     0     0     0

    0     1     0     0

如果 A(i,j) == 1，则可以形成 (i,j) 对并且如果 A(i, j)==0 则不可能形成 (i,j) 对。例如，(1,2) 是一个可能的对，因为 A(1,2)==A(2,1)==1 但 ( 3,4) 不是可能的对，因为 A(3,4)==A(4,3)==0。

问题来了。假设集合 N 中的一个成员只能与集合 N 中至多一个不同的成员成对(即，如果 1 与 2 形成一对，则1 不能与 3) 成对。我怎样才能找到可能对的所有可能“列表”？在上面的示例中，一个“列表”将仅包含 (1,2) 对。如果形成了这一对，则不可能形成任何其他对。另一个“列表”是:((1,3),(2,4))。我搜索了论坛，发现后一个“列表”是可以找到的最大匹配，例如，通过使用二分图方法。但是，我不一定只对找到最大匹配感兴趣；我有兴趣找到可能对的所有可能“列表”。另一个例子:

A =

    0     1     1     1

    1     0     0     1

    1     0     0     0

    1     1     0     0

在这个例子中，有三个可能的列表:

   (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