How can I generate all permutations of a matrix, in which value "1" cannot be repeated in any column or row? Rest of the elements are identical, and a number between 0 and 1.

Each row must have at least an element with value 1.

Say we have 3 by 4 matrix. Then an acceptable arrangement would be:

 x  x  1  x
 x  x  x  1
 x  1  x  x

and there will be:

 4! / (4-3)! = 24

different allowed permutations of a 3 by 4 matrix.

Say for a 4 by 5 matrix, violations would be

 1  x  x  x  1
 x  x  x  x  x
 x  x  x  1  x
 x  x  x  1  x

where first row has more than one values of 1, and column 4 has the same violation. Lastly, there is no 1 value in row 2.

Similarly number of allowed permutations would be:

 5! / (5-4)! = 120

that is, the number of different matrices.

My attempt is through different for loops, which is cumbersome for larger elements. Any smarter way to make this happen?

Thank you.

Answer 1

[Roger Stafford]

I don’t know how you want to arrange all the matrices that are to be generated so I leave that aspect to you. Suppose you wish to generate all m-by-n matrices using the value x where m<=n. First create the matrix A:

   A = toeplitz([1,repmat(x,1,m-1)],[1,repmat(x,1,n-1)]);

Next do this:

   P = perms(1:m);
   T = nchoosek(1:n,m);
   C = zeros(size(T,1),n);
   for k = 1:size(C,1)
     C(k,[T(k,:),setdiff(1:n,T(k,:))]) = 1:n; % <-- Corrected
   end

Now for every combination of ix in 1:size(P,1) and jx in 1:size(C,1) create

   A(P(ix,:),C(jx,:))

There will be n!/(n-m)! of these altogether. If m>n, do this the other way around.

[Bidsitlov]

I tweaked your answer a bit so that it completely generates a list:

 function [matrixlist] = allpermsALT(dim1,dim2,J)

 %m=dim1 n=dim2
 howmuch = factorial(dim2) / factorial(dim2 - dim1);
 matrixlist = cell(howmuch,1);

 offdiag = exp(-J);
 A = toeplitz([1,repmat(offdiag,1,dim1-1)],[1,repmat(offdiag,1,dim2-1)])
 P = perms(1:dim1);
 T = nchoosek(1:dim2,dim1);
 C = zeros(size(T,1),dim2);

 for k = 1:size(C,1)
     C(k,:) = [T(k,:),setdiff(1:dim2,T(k,:))];
 end

 counter = 1;
 for i = 1:size(P,1)
    for j = 1:size(C,1)
        matrixlist{counter,1} = A(P(i,:),C(j,:));
        counter = counter + 1;
    end 
 end

 end

It was instrutive to see an alternative way. Thank you for your answer!

[Roger Stafford]

I’m afraid I made an error on that code for C. I have corrected it in my answer. As it stood it would duplicate certain matrices and omit others.

Answer 2

[Bidsitlov]

Alright, so personal solution is below:

 function [matrixlist] = allperms(dim1,dim2,J)

 howmuch = factorial(dim2) / factorial(dim2 - dim1);
 matrixlist = cell(howmuch,1);

 trfm = trfmgod(dim1,dim2,J);
 blank = linspace(1,dim2,dim2);
 diff = dim1 + 1;

 for i=diff:dim2
    if blank(i) >= diff
        blank(i) = diff;
    end
 end

 perm_list  = unique(perms([blank]),'rows');
 listlength = length(perm_list);

 for j = 1:listlength
    matrixlist{j,1} = trfm(:,perm_list(j,:));
 end

 end

Function 'trfmgod' is a function, which initially yields, say for 3 by 5 matrix:

 1  x  x  x   x
 x  1  x  x  x
 x  x  1  x  x

x is a number generated by a J value, and, value 'howmuch' is calculated mathematically, giving number of allowed permutations.

Since in initial matrix, columns after the 'square portion' keeps repeating itself, parameter 'blank' should be [1 2 3 4 4] in our case.

Finally permutation list is generated by the 'blank' parameter, and a for loop generates all possible permutations.

If you have a better answer that would be informative.

Thank you.