MATLAB的答案

递归生成置换矩阵

10视图(30天)
汤姆
汤姆 2014年10月3日
回答: 罗杰·斯塔福德 2014年10月5日
你好,
一些代码的一部分我写我需要为给定的生成所有可能的矩阵大小m x n,必须有一个“1”在每一行和每一列不超过一个“1”。(我相信这些被称为置换矩阵)。列的数量有一个' 1 ',和其余的条目是0。程序将检查当前矩阵是否满足特定需求之前移动到下一个。
所以对于一个3 x4矩阵与3列' 1 ',我想需要生成以下:
[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]- >等
[0 1 0 0][0 0 1 0][0 0 1 0]
使用嵌套循环我知道我可以这样做,但从google这样可以实现递归地使用深度优先搜索…有人知道如何做到这一点在Matlab ?
谢谢你！

在回答这个问题。

答案(2)

罗杰·斯塔福德
罗杰·斯塔福德 2014年10月5日
下面生成所有可能的矩阵M满足您的需求。而且他们不需要测试,因为每一个生产是保证有效。在生产时如何处理M在for循环。
C = nchoosek (0: m: m * (n - 1), m);
P =烫发(1:m);
为ic = 1:尺寸(C, 1)
为ip = 1:尺寸(P, 1)
M = 0 (M, n);
:M (P (ip) + C (ic,:)) = 1;
%做任何你想做的
结束
结束
杰夫•海斯
杰夫•海斯 2014年10月5日
汤姆,你可以试试下面的递归函数将所有列,这样所有米列的排列。
函数[allPerms] = permuteCols (A)
allPerms = {};
= 1;
%停止条件
如果大小(2)= = 1
%只有一列就返回它
allPerms{} =一个;
其他的
%迭代矩阵的每一列
为k = 1:尺寸(2);
% k列
坳= (:,k);
%去除B k列
B =一个;
B (:, k) = [];
%其余列排列
= permuteCols子集(B);
%每个组合并添加前缀列allPerms集
为m = 1:长度(子集)
allPerms {} = {m}][坳子集;
在= + 1;
结束
结束
结束
结束
用你的例子中,我们能做的
allPerms = permuteCols(眼(3,4));
在哪里 allPerms 将所有24安排四列的输入矩阵 (3、4) 。然而,性能降低的列数增加。如果有 米 列输入矩阵,然后有 米! 输入矩阵的列的排列。

类别

找到更多的在性能和内存在帮助中心和文件交换

标签

社区寻宝

找到宝藏在MATLAB中央,发现社区如何帮助你!

开始狩猎!