From a matrix, Pick one element from each row and not from same column for all possibilities. Only for non zero elements.

Hi, From a matrix, I would like to pick one element from each row and not from same column for all possibilities.

Only for non zero elements.

Example, from A = [1 2 0; 1 2 0; 0 0 3], I want to obtain (1 2 3 and 2 1 3).

Thank you

Answer 1

[Puru Kathuria]

Hi,

Your requirements are answered in a similar question mentioned in this link. Also, selecting set of elements from a matrix such that each element comes from distinct row and column can also be modeled as a Matching problem. (graph theory)

[MeMariah]

Thank you Puru Kathuria.

Answer 2

[Bruno Luong]

A dynamic programming for fun

function p = nzperm(A,c)

if nargin < 2
    c = 1;
end
r = find(A(:,c));
if isempty(r)
    p = [];
elseif c==size(A,2)
    p = A(r,c); % p = r(:);
else
    p = [];
    for i=r.'
        Ai = A;
        Ai(i,:) = 0;
        q = nzperm(Ai,c+1);
        a = A(i,c); % a = i
        q = [a+zeros(size(q,1),1) q];
        p = [p; q]; %#ok
    end
end

Result

>> A=rand(5); A = A.*(rand(size(A))>0.6)

A =

         0    0.6468    0.7881    0.5598    0.8008
    0.5607         0         0         0    0.8961
         0         0         0    0.9394    0.5975
         0    0.4756    0.1335         0         0
         0    0.3625    0.0216         0    0.9437

>> nzperm(A)

ans =

    0.5607    0.6468    0.1335    0.9394    0.9437
    0.5607    0.4756    0.7881    0.9394    0.9437
    0.5607    0.4756    0.0216    0.5598    0.5975
    0.5607    0.4756    0.0216    0.9394    0.8008
    0.5607    0.3625    0.1335    0.5598    0.5975
    0.5607    0.3625    0.1335    0.9394    0.8008

Note: this code will be slow on large array, since MATLAB make copies of matrix at every step. This algorithm could be implemented without copy using C mex.

[MeMariah]

Thank you so much Bruno Luong, this is really helpful.

[MeMariah]

Hello Bruno,

What modification can I make if I were intstead interested in only zero elements. for example

A = [1 0 0; 0 2 0; 0 0 3] to obtain [2 3 1;3 2 1]?

Thanks.

[Bruno Luong]

Modifications: uncomment the two statements "%..." and change function name

function p = zperm(A,c)
if nargin < 2
    c = 1;
end
r = find(A(:,c));
if isempty(r)
    p = [];
elseif c==size(A,2)
    p = r(:);
else
    p = [];
    for i=r.'
        Ai = A;
        Ai(i,:) = 0;
        q = zperm(Ai,c+1);
        a = i;
        q = [a+zeros(size(q,1),1) q];
        p = [p; q]; %#ok
    end
end

Test

>> A = [1 0 0; 0 2 0; 0 0 3]

A =

     1     0     0
     0     2     0
     0     0     3

>> zperm(~A) % CAREFUL, call with ~A (NOT(A)) and NOT A

ans =

     2     3     1
     3     1     2

[MeMariah]

You are a genius, am so grateful.

[MeMariah]

@Bruno, you are right. large array take long. Unfortunately, I keep getting error when I try to generate the C mex file. Am using this app for the first time. Are able to help? error points to the line with

for i= r.'

Thanks.