在Matlab中查找可能的對的所有可能的「列表」

我一直在思考過去幾天的問題，但由於我是MATLAB的初學者，所以我不知道如何解決它。這是背景。假設您有一個對稱的N×N矩陣，其中每個元素是0或1和N = (1,2,...,n)。在Matlab中查找可能的對的所有可能的「列表」

例如：

如果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))。我搜索了論壇並發現後者「列表」是可以找到的最大匹配，例如通過使用二分圖方法。但是，我不一定只對找到最大匹配感興趣;我有興趣找到所有可能的「列表」可能的對。又如：

在這個例子中，有三個可能的列表：

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

我希望你能明白我的問題，我很抱歉，如果我不清楚。我很感激所有我能得到的幫助。非常感謝！

來源

2014-03-19 user3436833

這可能是一個快速的方法。

代碼

%// 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

輸出

EDIT 1

基本上我將計算所有的矩陣的成對指數以滿足設定的標準這個問題然後簡化y將它們映射到給定的矩陣上。尋找「有效」指數的部分顯然是其中乏味的部分，並且在處理尺寸大於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

輸出

來源

2014-03-19 10:22:36 Divakar

由於羅迪Oldenhuis和Divakar都爲你快速的答覆！我有一個問題Divakar：如果我嘗試你的矩陣解決方案 A = [0 1 1 1; 1 0 1 1; 1 1 0 1; 1 1 1 0] 輸出是 ans = [1 2; 2 3; 3 4] ，ans = [1 3; 2 4] ，ANS = [ 4]，在這種情況下，然而，這三種可能的「列表」是：（（1,2），（3,4）），（（1,3），（2,4））和（（1,4），（2,3））在輸出中是否存在某些我誤解的內容。再一次，非常感謝。 – user3436833

+1，這比我的笨多了:) –

@ user3436833和Rody，我可能誤解了整件事！也許編碼起來太快了，讓我們來看看！ – Divakar

我敢肯定有一個更快的方式做到這一點，但這裏的顯而易見的解決方案：

%// 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

來源

2014-03-19 10:02:22

在Matlab中查找可能的對的所有可能的「列表」

回答

相關問題