4

如果我有一个矩阵：

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

我想将非零元素提取到一些批次中，关于一个规则：如果一个元素已经被采用，则不允许同一行/列中的另一个元素。所以提取的矩阵将是：
第一批： 

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 中做到这一点？

4

3 回答 3

3

对于行，我会这样做：

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

  1. 检查数字是否非零：

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

  2. 沿 的行取cumsumAnonzero：

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

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

  3. 将零值的索引设置回零，因此它们不会被选中

    A(~Anonzero)=0;

  4. 提取批次：

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

导致：

>>batch{1}
    0     0     3     0
    4     0     0     0
    2     0     0     0

>>batch{2}
    0     0     0     4
    0     3     0     0
    0     0     2     0

>>batch{3}
    0     0     0     0
    0     0     2     0
    0     0     0     0

我认为对于行和列规则可以做类似的事情，但我没有马上看到它。我会考虑的；）

于 2012-08-24T08:55:57.500 回答
2

冈瑟已经走在正确的轨道上。你想选择一个元素，如果

  1. 非零的行 cumsum 为 1 AND
  2. 非零的列 cumsum 为 1 AND
  3. 元素本身不为零。

下面的代码解决了这个问题：

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

返回这些批次。

batches{:}
ans =
     0     0     0     4
     0     0     2     0
     2     0     0     0

ans =
     0     0     3     0
     4     0     0     0
     0     0     0     0

ans =
     0     0     0     0
     0     3     0     0
     0     0     2     0

所以它至少适用于这个小测试用例。

于 2012-08-24T13:36:24.490 回答
2

毫无疑问，一个有趣的问题......我的猜测是@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-24T09:02:15.583 回答