如何获得矩阵的所有可能的置换矩阵

Question

我需要为一个矩阵创建所有可能的置换矩阵，其中每个置换矩阵在每一列和每一行仅包含一个 1，而在所有其他位置仅包含一个 0。

例如，下面的示例 (1) 是 2x2 矩阵的所有可能置换矩阵，(2) 是 3x3 矩阵的所有可能置换矩阵，依此类推

那么如何在MATLAB中得到一个NxN矩阵的这些矩阵并存入一个三维矩阵呢？

Answer 1

这是我的解决方案，使用 implicit expansion（使用 Octave 5.2.0 和 MATLAB Online 测试）：

n = 3;

% Get all permutations of length n
p = perms(1:n);

% Number of permutations
n_p = size(p, 1);

% Set up indices, where to set elements to 1
p = p + (0:n:n^2-1) + (0:n^2:n^2*n_p-1).';

% Set up indices, where to set elements to 1 (for MATLAB R2016a and before)
%p = bsxfun(@plus, bsxfun(@plus, p, (0:n:n^2-1)), (0:n^2:n^2*n_p-1).');

% Initialize 3-dimensional matrix
a = zeros(n, n, n_p);

% Set proper elements to 1 
a(p) = 1

n = 3 的输出：

a =

ans(:,:,1) =

   0   0   1
   0   1   0
   1   0   0

ans(:,:,2) =

   0   1   0
   0   0   1
   1   0   0

ans(:,:,3) =

   0   0   1
   1   0   0
   0   1   0

ans(:,:,4) =

   0   1   0
   1   0   0
   0   0   1

ans(:,:,5) =

   1   0   0
   0   0   1
   0   1   0

ans(:,:,6) =

   1   0   0
   0   1   0
   0   0   1

Answer 2

使用 repelem、perms 和 reshape：

n   = 3;                                 % matrix size 
f   = factorial(n);                      % number of permutation
rep = repelem(eye(n),1,1,f)              % repeat n! time the diagonal matrix
res = reshape(rep(:,perms(1:n).'),n,n,f) % indexing and reshaping

其中 res 是：

res =

ans(:,:,1) =

   0   0   1
   0   1   0
   1   0   0

ans(:,:,2) =

   0   1   0
   0   0   1
   1   0   0

ans(:,:,3) =

   0   0   1
   1   0   0
   0   1   0

ans(:,:,4) =

   0   1   0
   1   0   0
   0   0   1

ans(:,:,5) =

   1   0   0
   0   0   1
   0   1   0

ans(:,:,6) =

   1   0   0
   0   1   0
   0   0   1

根据您的评论：

What I need to do is to multiply a matrix i.e Z with all possible permutation matrices and choose that permutation matrix which resulting a tr(Y) minimum; where Y is the results of multiplication of Z with the permutation matrix. I Think I don't need to generate all permutation matrices and store them in such variable, I can generate them one by one and get the result of multiplication. Is that possible ?

您正在尝试解决分配问题，您可以使用众所周知的hungarian algorithm在多项式时间内解决此任务。无需生成置换矩阵的 googleplex。

如何获得矩阵的所有可能的置换矩阵

How to get all possible permutation matrices of a matrix

matlab

permutation

matrix