当前位置 博文首页 > xuanzhigu的博客:matlab 从多个数组中选取一个,产生所有排列组
在建模过程中遇到了这个问题,但在网上没有找到任何解决问题的方法,所以自己想了三天终于大彻大悟,特此分享一下。
当然这类问题最好不要用这种枚举的方法,时间复杂度为n的m次方,不能称得上是个好的算法,要具体问题具体分析。
这个问题就是在数组少时可以通过手写来解决
例如我们要排列的是a=[15 32 56 74]、b=[469 85 26 49 ] 可以通过:
a=[15 32 56 74]
b=[469 85 26 49 ]
m=1;
for i=a
for j=b
temp{m}=[i,j];
m=m+1;
end
end
但 当数组比较多或者是n的时候就无法用手写的方式来解决了。
整体的思路就是循环嵌套,写一个程序自己调用自己,一直调用到最后一个数组,为了能够让每一个数组都调用一个数,必须产生一个全局变量来加以限制。为了保存每一个产生的组合,要定义一个全局变量的元胞数组,同样让每一次的存储地址加一也要声明全局变量的地址。
matlab实现功能的主程序为:
clc
clear all
dd=[8,12,5,3;
1 ,2, 3 ,4;
17 85 65 66];%这里每一行作为一个数组;便于书写,如果长度不一,可以直接复制给下面的aaa元胞数组
nx=size(dd,1);
ny=size(dd,2);
for i=1:nx
[aaa{i} ]=sort_change( dd(i,:) )
end
xxx=1 ; %行数
yyy=[];
global nnn; %组合序号
nnn=1;
global zuhe; %存放所有组合
zuhe={};
temp=zeros(1,nx);
for i=aaa{xxx}
yyy(xxx)=i ;
diedai( aaa, xxx, nx, yyy);
end
function []=diedai(aaa,xxx,nx,yyy)
global zuhe
global nnn
xxx=xxx+1;;
for i=aaa{xxx}
yyy(xxx)=i;
if length(yyy)-length(unique(yyy))>0
continue;
end
if xxx<nx
diedai(aaa,xxx,nx,yyy);
end
if xxx==nx
zuhe{nnn}=yyy;
nnn=nnn+1;
end
end
end
function [ shu]=sort_change(temp)
[a,b]=sort(temp) ;
shu=a;
% shunxu=b(1:3)
end
得到的元胞数组结果:
你可能会问了,4×4×4 ,不应该是64个组合吗,我这里把组合中有重复的组合进行了删除,在递归调用的过程之中加入了判断,在最优化问题中通常会出现不能产生重复的要求。还有为什么组合组合是每一个数组从小大大抽取的,这是在解决最优化问题时找出最小组合写的,删减了不少附带的条件,来专门解释排列组合问题。
当然要是需要不删除重复数字的全排列也可以自行更改条件。
少熬夜,追光者。
cs