Matlab에서 가능한 모든 "목록"찾기.

Question

지난 며칠 동안 문제에 대해 생각해 봤지만 MATLAB 초보자인데 해결 방법이 없습니다. 다음은 배경입니다. 각 요소가 0 또는 1이고 N = (1,2,...,n) 인 대칭 N×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 

EDIT 기본적 1

I가 설정된 조건을 만족하는 행렬의 모든 페어 와이즈 지수를 계산할 질문과 간단한 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 

출력

귀하의 빠른 회신 RODY Oldenhuis 및 Divakar 모두

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