Recursively generating permutation matrices

3 次查看（过去 30 天）
Tom
Tom 2014-10-3
回答： Roger Stafford 2014-10-5
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!

请先登录，再回答此问题。

回答（2 个）

Roger Stafford
Roger Stafford 2014-10-5
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
Geoff Hayes
Geoff Hayes 2014-10-5
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.

类别

在 Help Center 和 File Exchange 中查找有关 Design of Experiments (DOE) 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by