我前面写过一种方法生成全排列,现在看用DP的方法解决。
参考
How to generate permutations 看前面的那种解法。
DP的思路就是生成N个数的全排列,先考虑生成前面N-1个数字的全排列,然后把最后一个数字插入上一步每个结果的每个缝隙中,形成最后的结果。用perl比较好操纵数组,写起来的程序比较简单。(可惜这个博客不支持perl语法高亮啊)
use strict;
use warnings;
sub permutation {
my (@array) = @_;
my $length = scalar @array;
if($length == 1){
#如果数组就一个元素,返回的结果集合里面只有一个单元素数组
return [\@array];
}else {
#取出最后一个元素
my $tail = pop(@array);
#求解N-1个数字的全排列
my $sub_results = permutation(@array);
my $new_results = [];
foreach my $sub_result (@$sub_results){
my $pos = 0;
#取出的最后的那个元素可以插在0,1..$length-1等处
while($pos < $length){
my @new_result = @$sub_result;
#插入尾元素,形成新的数组
splice(@new_result, $pos, 0, $tail);
$pos++;
#收集结果
push @$new_results, \@new_result;
}
}
return $new_results;
}
}
sub main {
my @a = (6,7,8,9);
my $results = permutation(@a);
foreach my $result (@$results){
print join(',', @$result) . "\n";
}
}
main;
输出如下:
9,8,7,6
8,9,7,6
8,7,9,6
8,7,6,9
9,7,8,6
7,9,8,6
7,8,9,6
7,8,6,9
9,7,6,8
7,9,6,8
7,6,9,8
7,6,8,9
9,8,6,7
8,9,6,7
8,6,9,7
8,6,7,9
9,6,8,7
6,9,8,7
6,8,9,7
6,8,7,9
9,6,7,8
6,9,7,8
6,7,9,8
6,7,8,9
相比之下,这种思路要简单多了. 性能就要在考虑了.
分享到:
相关推荐
用序数法生成全排列,java语言,希望有帮助
C++学的递归的全排列 当n>10 效率会很低 这个请注意
采用matlab语言编写高效程序,实现快速又高效的生成全排列矩阵算法
资源名:生成全排列矩阵_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定经验的开发...
C语言的全排列 注意 当n>10 效率会非常低
全排列的生成算法
可直接运行 MATLAB生成全排列矩阵算法 程序源代码.rar
字典序法生成全排列,希望对学习组合数学的同学有帮助
利用C++实现的全排列生成算法~~实现数据全排列~
组合数学中的全排列问题,在此提供几种常用方法的解法~~~
matlab经典算法的程序-生成全排列矩阵.zip
字典序、邻位对换、递归递增进位制数法、递归的递减进位制数法生成全排列。除递归地增是O(n·n!)外,其余三个都是O(n!)。main函数是计算1——12生成全排列的运行时间。
全排列acc pascal程序加题解 全排列 Time Limit:20000MS Memory Limit:65536K Total Submit:506 Accepted:218 Description 列出所有数字1到数字n的连续自然数的排列,要求所产生的任一数字序列中不允许出现得复...
这是组合数学的全排列生成算法,用C语言实现的,包括四种常见的全排列生成算法,字典序法,循环左移,循环右移,邻位对换的方法。
【问题描述】输入整数N( 1 ),生成从1~N所有整数的全排列。 【输入形式】输入整数N。 【输出形式】输出有N!行,每行都是从1~N所有整数的一个全排列,各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循...
此程序是在密码学中经常用到的随机全排列(可用以作为“代替表”或“置换”)的方法
全排列生成算法中的字典序法的vc++源码
题目描述:给定一个数列a1,a2,a3…an,输出他所有的全排列。 算法设计描述: 1、获取当前的一种排列,用start,end分别表示该排列的列头,列尾; 2、判断start是否和end相等,若相等,执行3,否则执行4; 3、将当前...
字典序、邻位对换、递增进位制数,递减进位制数以及两种递归算法的C++实现,包含代码和exe文件,供大家参考!