递归算法
function testperm(ss, s1, s2)
global v;
if isempty(s1) && isempty(s2)
v(size(v, 1) + 1, :) = ss;
else
if ~isempty(s1)
testperm([ss s1(1)], s1(2:end), s2);
end
if ~isempty(s2)
testperm([ss s2(1)], s1, s2(2:end));
end
end
运行的时候执行如下命令:
clear global v; % 清除原有的全局变量v
testperm([], 'abcdefgh', '12345678');
global v; % 把全局变量在workspace中显示出来
v=char(v); % 把v从double矩阵变成string数组
这两个长度都是8的字符串在我的电脑上耗时10秒,结果v是一个12870*16的矩阵。当然为了效率,还可以把递归转化为不递归,只不过程序会复杂一些。
此算法的好处是不需要计算全排列,内存消耗和运行时间都极大减少。 你可以试着记录全排列长度16的字符串消耗的时间,再跟我这个两个长度为8的字符串消耗时间做个对比。
程序太长了,我弄了几次都没有成功,我将它放在了我的空间上,你可以链接去复制下来
http://hi.baidu.com/carrot_hy/blog/item/589ebb0a5ee0343ee82488ff.html
附上一小段
%InsertPerms.m用来得到穿插排列,并保持原各字符串中顺序
%屏幕提示输入字符串StrA,StrB
%输出中InStr为所求矩阵
clc;clear;
StrA=input('Please Enter a String Vector
StrB=input('Please Enter a String Vector
StrAn=length(StrA); %字符串StrA的长度
StrBn=length(StrB); %字符串StrB的长度
%建立一个长为两字符串合起来长的索引,前一部分为StrA索引,后一部分为StrB索引
A=perms(['123abcd']);
[m,n]=size(A);
S=A;
k=0;
for i=1:m
a1=findstr(A(i,:),'1');
a2=findstr(A(i,:),'2');
a3=findstr(A(i,:),'3');
aa=findstr(A(i,:),'a');
ab=findstr(A(i,:),'b');
ac=findstr(A(i,:),'c');
ad=findstr(A(i,:),'d');
if ((a1
S(k,:)=A(i,:);
end
end
S=S(1:k,:)
S =
abcd123
abc123d
abc12d3
abc1d23
ab123cd
ab12cd3
ab12c3d
ab1c23d
ab1c2d3
ab1cd23
a1b23cd
a1b2cd3
a1b2c3d
a1bc23d
a1bc2d3
a1bcd23
a123bcd
a12b3cd
a12bcd3
a12bc3d
1abc23d
1abc2d3
1abcd23
1ab23cd
1ab2c3d
1ab2cd3
1a23bcd
1a2b3cd
1a2bc3d
1a2bcd3
12ab3cd
12abc3d
12abcd3
12a3bcd
123abcd
这个可能归算法管。
哈哈。