Recursively generating permutation matrices

Hi,

As part of some code I'm writing I need to generate all possible matrices for a given size m x n, where there must be exactly one '1' in each row and no more than one '1' in each column. (I believe these are known as permutation matrices.) The number of columns having a '1' is given, and the rest of the entries are 0s. The program will then checks if the current matrix meets specific requirements before moving on to the next one.

So for a 3x4 matrix with 3 columns having a '1', I would need to generate the following:

[1 0 0 0]    [1 0 0 0]    [1 0 0 0]    [1 0 0 0]    
[0 1 0 0] -> [0 1 0 0] -> [0 0 1 0] -> [0 0 1 0] ->
[0 0 1 0]    [0 0 0 1]    [0 1 0 0]    [0 0 0 1]

[1 0 0 0]    [1 0 0 0]    [0 1 0 0]
[0 0 0 1] -> [0 0 0 1] -> [1 0 0 0] -> etc
[0 1 0 0]    [0 0 1 0]    [0 0 1 0]

I know I could do this using nested loops, but from Googling it looks like this could be implemented recursively using a depth first search... Does anyone know how to do this in Matlab?

Thank you!

Answer 1

[Roger Stafford]

The following generates every possible matrix M satisfying your requirements. Moreover they don't need testing, since every one produced is guaranteed to be valid. What to do with M when it is produced within the for-loops is up to you.

   C = nchoosek(0:m:m*(n-1),m);
   P = perms(1:m);
   for ic = 1:size(C,1)
     for ip = 1:size(P,1)
       M = zeros(m,n);
       M(P(ip,:)+C(ic,:)) = 1;
       % Do whatever you want to do with M
     end
   end

Answer 2

[Geoff Hayes]

Tom - you could try the following recursive function that rearranges all columns so that all permutations of the m columns are considered.

 function [allPerms] = permuteCols(A)

    allPerms = {};
    at  = 1;

    % stopping condition
    if size(A,2)==1
        % only one column so just return it
        allPerms{at} = A;
    else
        % iterate over each column in the matrix
        for k=1:size(A,2);

            % grab the kth column
            col    = A(:,k);

            % remove the kth column from B
            B      = A;
            B(:,k) = [];

            % permute the remaining columns
            subSet = permuteCols(B);

            % prefix the column to each combination and add to allPerms set
            for m=1:length(subSet)
               allPerms{at} = [col subSet{m}]; 
               at      = at + 1;
            end
        end
    end
 end

Using your example, we could do

 allPerms = permuteCols(eye(3,4));

where allPerms would be all 24 arrangements of the four columns of the input matrix eye(3,4). However, the performance degrades as the number of columns increase. If there are m columns in your input matrix, then there are m! permutations of the columns of that input matrix.