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

2番目のバッチ： 

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

3番目のバッチ： 

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. の行に沿ってcumsumを取りますAnonzero：

    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

興味深い問題は間違いありません...私の推測では、@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 に答える
2

ガンサーはすでに正しい軌道に乗っていた。要素を選択する場合は、

  1. 非ゼロの行の累積は1AND
  2. 非ゼロの列の累積は1AND
  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

ただし、2番目のバッチは次のようになっているため、返されるソリューションは最適ではないことに注意してください。

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

これは、残りの行列要素が同じ列からのものであることを意味します。

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

残念ながら、同じバッチでそれらを描画することはできません。したがって、3つではなく4つのバッチになります。

編集：おそらく、ゼロ以外の多くの行/列に表示される要素を最初に選択することをお勧めします。たとえば、これらの重みを使用できます

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 に答える