Speeding up Binary Matricies Generation with given conditions

Need help speeding up my code that produces 3x3 Binary Matrix only if it meets all the fixed row and column sums. It currently times out a lot before it generates the matrix and I need to get it faster to modify it for a 5x5. Also want to mention that there is probably a few things wrong in my code, and that is because I am a beginner a small idea on how I am forcing it to work.

rows = 3;
  columns = 3;
  C1=2;  %Fixed Column Sums
  C2=3;
  C3=1;
  R1=1;  %Fixed Row Sums
  R2=2;
  R3=3;
  % Initialize matrix.
  m=randi([0 1],rows,columns);

    for k=1:rows,

    end
        runtest = 0 ; 
    while runtest < 10000000 ;
        runtest = runtest + 1 ;
        % randomly swap columns
        for k=1:columns,
            p = randperm(rows);
            m(k,:) = m(k,p);
        end
    if (sum(m(:,[1])) == C1) && (sum(m(:,[2])) == C2) && (sum(m(:,[3])) == C3)...
    && (sum(m([1],:)) == R1) && (sum(m([2],:)) == R2) && (sum(m([3],:)) == R3);
                     break ;
                 end
    end
    R_1 = m(1,1) + m(1,2) + m(1,3);
    R_2 = m(2,1) + m(2,2) + m(2,3);
    R_3 = m(3,1) + m(3,2) + m(3,3);
    %Summing up all the Rows into a array to read
    RowsSums= [ R_1 R_2 R_3 ];
    C_1 = m(1,1) + m(2,1) + m(3,1);
    C_2 = m(1,2) + m(2,2) + m(3,2);
    C_3 = m(1,3) + m(2,3) + m(3,3);
    %Summing up all the Columns into a array to read
    ColumnSums= [ C_1 C_2 C_3 ];
    if runtest < 10000000
    m
    RowsSums
    ColumnSums
    else
        disp('No matrix found within time') ;
    end}

Answer 1

[Roger Stafford]

There is a flaw in the strategy of your code. If at the step

   m = randi([0 1],rows,columns);

it does not yield exactly six 1's, you will never succeed in satisfying your sum constraints afterwards using only permutations within each row. At the very least you need to ensure that six 1's in total, no more, no less, are present in the 'm' matrix before you begin with the permutations.

The next problem is that your permutation procedure only permutes elements within each row, which doesn't change the sum of that row. Only a permutation within each column could do that. Hence you need both kinds of permutations, one within rows and one within columns.

You could avoid using the for-loop by making single permutations of the nine elements in 'm' using linear indices. Also this would eliminate the necessity of two kinds of permutations.

   m = [ones(1,6),zeros(1,3)];
   while ....
     m = reshape(m(randperm(9)),3,3);
     % check sums
   end

Actually it might be easier to leave m always a 1 x 9 row vector to avoid all the 'reshapes' and modify the sum checking procedure accordingly:

   sum(m(1:3:7))==R1, etc.

[Eric Noname]

Thanks Roger. This works for my 3x3 matrices and the concept and code worked for my 5x5 matrices. I'm a little confused on what that 7 refers to in your last code to modify the checking procedure. Now that I have generated the right matrices I am going to work on calculate the number of possible matrices for a given set of fixed columns and rows. But I want to try working it out myself before pleading for help. Thanks.

[Roger Stafford]

These expressions are equivalent:

   sum(m(1:3:7))==R1
   sum(m([1,4,7]))==R1
   sum([m(1),m(4),m(7)])==R1
   m(1)+m(4)+m(7)==R1

where m is now a 1-by-9 row vector in accordance with that last idea I put forth which would be equivalent to checking the first row sum of the original 3-by-3 version of m: m(1,1)+m(1,2)+m(1,3)==R1.

You can read about the equivalence of linear indices to matrix indices at the site:

   http://www.mathworks.com/help/matlab/math/matrix-indexing.html