提取矩阵元素

如果我有一个矩阵：提取矩阵元素

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 –

提取矩阵元素

回答

相关问题