提取矩陣元素

如果我有一個矩陣：提取矩陣元素

0 0 3 4 
4 3 2 0 
2 0 2 0

我要提取的非零元素到一些批次中，相對於一個規則：如果一個元件已被使用，在另一元件相同的行/列是不允許的。這樣提取出的矩陣將是：
第1批：

0 0 3 0 
4 0 0 0 
0 0 0 0

第二批：

0 0 0 4 
0 3 0 0 
0 0 2 0

第三批次：

0 0 0 0 
0 0 2 0 
2 0 0 0

批次的任何其它組合也是可以接受的，只要因爲所有非零元素都被覆蓋了，並且規則是一致的。你如何在MATLAB/Octave中做到這一點？

來源

2012-08-24 Nicolas Moreau

Gunther已經走上了正軌。你要選擇一個元素，如果

非零的行cumsum爲1 和
非零的列cumsum爲1 和
元素本身是非零。

下面的代碼解決了這個問題：然而

A = [0, 0, 3, 4; 
    4, 3, 2, 0; 
    2, 0, 2, 0]; 

batches = cell(0); 
while any(A(:)~=0) 
    selector = cumsum(A~=0, 1) .* cumsum(A~=0, 2) .* (A~=0) == 1; 
    batches{end+1} = A .* selector; 
    A(selector) = 0; 
end

注意，由於它的第二批是

0 0 0 4 
0 3 0 0 
2 0 0 0

這意味着返回的解決方案不是最佳的剩餘矩陣元素是從同一列：

0 0 0 0 
0 0 2 0 
0 0 2 0

不幸的是，你不能在同一批次中繪製它們。所以你最終得到四批而不是三批。

編輯：也許，這是一個好主意，首先選擇這些元素，這些元素出現在具有很多非零的行/列中。例如，可以使用這些權重

weight = repmat(sum(A~=0, 1), size(A, 1), 1) ... 
     .* repmat(sum(A~=0, 2), 1, size(A, 2)) .* (A~=0) 

weight = 
    0  0  6  2 
    6  3  9  0 
    4  0  6  0

下面的算法

batches = cell(0); 
while any(A(:)~=0) 
    batch = zeros(size(A)); 
    weight = repmat(sum(A~=0, 1), size(A, 1), 1) ... 
      .* repmat(sum(A~=0, 2), 1, size(A, 2)) .* (A~=0); 
    while any(weight(:)~=0) 
     [r,c] = find(weight == max(weight(:)), 1); 
     batch(r,c) = A(r,c); 
     A(r,c) = 0; 
     weight(r,:) = 0; 
     weight(:,c) = 0; 
    end 
    batches{end+1} = batch; 
end

返回這些批次。

所以它至少在這個小測試案例中起作用。

來源

2012-08-24 13:36:24 Mehrwolf

現在好了，那個循環看起來非常熟悉...... :) –

@Rody：是的。對你的算法結構和我的權重感謝;-) – Mehrwolf

順便說一句，我認爲總結repmats而不是乘以它們可能會更好。 – Mehrwolf

對於剛行，我會如下做到這一點：

A = [ 0 0 3 4 ; 
     4 3 2 0 ; 
     2 0 2 0 ];

檢查，如果數字是非零：

Anonzero=A~=0; 
>> Anonzero 
    0  0  1  1 
    1  1  1  0 
    1  0  1  0

採取cumsum沿Anonzero行：

Aidx=cumsum(A,[],2); 
>> Aidx 
    0  0  1  2 
    1  2  3  3 
    1  1  2  2 

numbatches=max(Aidx(:,end));

零個值的設定指標回到零，所以他們不會得到選擇
```
A(~Anonzero)=0; 
```

提取批次：

batch=cell(numbatches,1); 
for ii=1:numbatches 
    batch{ii}=A.*(Aidx==ii); 
end

導致：

我假設可以做一些類似的行和列規則，但我沒有馬上看到它..我會考慮它;）

來源

2012-08-24 08:55:57

一個有趣的問題毫無疑問...我的猜測是@ GuntherStruyf的方法將最終成爲你應該選擇的方法。但是，這裏有一個簡單的採用溶液循環：

A = [ 
    0 0 3 4 
    4 3 2 0 
    2 0 2 0 ]; 

C = {}; 
nz = A ~= 0; 
while any(nz(:)) 

    tmpNz = nz; 
    tmpA = A; 
    newNz = false(size(nz));  
    while true 

     [i,j] = find(tmpNz, 1); 
     if isempty(i) || isempty(j), break; end 

     tmpNz(i,:) = false; 
     tmpNz(:,j) = false; 
     newNz(i,j) = true; 

    end 

    tmpA(~newNz) = false; 
    C{end+1} = tmpA; 
    nz(newNz) = false; 

end

這應該是比較快的，一旦你擺脫生長的細胞陣列，例如，通過與大量的初始元素的預分配，然後刪除之後未使用的元素。

儘管如此，我還是等到@GuntherStruyf把他的東西拿出來！

來源

2012-08-24 09:02:15

我沒有太多的空閒時間今天/下週末/下週，所以請隨時擴展我的解決方案：p –

提取矩陣元素

回答

相關問題