两个经典递归模板,以前写过,现在再过一遍!
基本思路:
如果题目给的输入时数组,首先先要把数组转为ArrayList,因为ArrayList可以很方便地插入,删除,添加!
其次,递归函数的形式都一样,一共有3个参数,分别叫ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret 。 done存放已经处理过的数据,rest存放还没处理的数据,ret存放最后的结果。注意这里的Integer可以是泛型,任意的data type。
具体思路:
全排列:对A[0,1,2,3...n] 每次依次取一个元素,添加到done里,然后对剩下的rest递归,直到rest为空。所以总的结构就是一个for循环里面,有一个从rest取数据,递归,撤销的过程。所以总结一下就是,每次递归,轮流从rest里取数据,依次添加到done。
子集:每次取出rest的第一个元素,然后做决定是否添加到done里面,可以添加,也可以不添加,所以会有两个递归。所以总结一下就是,每次递归,总是取rest的第一个数据,然后做两种选择。
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int[] A = {1,2,3};
subset(A);
permutation(A);
String s = "abc";
permutationStringRec(new StringBuilder(), new StringBuilder(s));
}
// ======================================================= permutation
public static void permutation(int[] A) {
ArrayList<Integer> rest = new ArrayList<Integer>();
ArrayList<Integer> done = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
for(int i : A) {
rest.add(i);
}
permutationRec(done, rest, ret);
System.out.println(ret);
}
public static void permutationRec(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret) {
if(rest.size() == 0) {
ret.add(new ArrayList<Integer>(done));
return;
}
for(int i=0; i<rest.size(); i++) {
int val = rest.get(i); // 选择第i个元素,添加到done
done.add(val);
rest.remove(i);
permutationRec(done, rest, ret);
rest.add(i, val);
done.remove(done.size()-1);
}
}
// ======================================================= subset
public static void subset(int[] A) {
ArrayList<Integer> rest = new ArrayList<Integer>();
ArrayList<Integer> done = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
for(int i : A) {
rest.add(i);
}
subsetRec(done, rest, ret);
System.out.println(ret);
}
public static void subsetRec(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret) {
if(rest.size() == 0) {
ret.add(new ArrayList<Integer>(done));
return;
}
int first = rest.remove(0);
// 选择添加到done
done.add(first);
subsetRec(done, rest, ret);
done.remove(done.size()-1);
// 选择不添加到done
subsetRec(done, rest, ret);
rest.add(0, first);
}
// ======================================== permutationStringRec 另一种用StringBuilder的变型版
public static void permutationStringRec(StringBuilder done, StringBuilder rest){
if(rest.length() == 0) {
System.out.println(done.toString());
return;
}
for(int i=0; i<rest.length(); i++) {
char c = rest.charAt(i);
done.append(c);
rest.deleteCharAt(i);
permutationStringRec(done, rest);
rest.insert(i, c);
done.deleteCharAt(done.length()-1);
}
}
}
分享到:
相关推荐
全排列算法有两个比较常见的实现:递归排列和字典序排列。 (1)递归实现 从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典...
全排列-基于递归实现
Problem B:Permutation with Repetition R={ r1,r2,… ,rn }是要进行排列的n 个元素。其中元素r1,r2,… ,rn可能相同。试设计一个算法,列出R的所有不同排列。 编程任务:给定n 以及待排列的n 个元素。计算出这n 个...
DFS搜索案例——寻找全排列。 深度优先遍历图的方法是,从图中某顶点v出发: (1)访问顶点v; (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问; (3)若此时图...
2017年计算机等级考试二级C++辅导:全罗列生成算法:next_permutation .docx
用于GAP的GRAPE 4.8.3软件包 GRAPE是Leonard H.Soicher编写的用于图形和组计算的GAP程序包,其中包括Steve Linton,Alexander Hulpke,Jerry James和Max Horn的贡献,其中包括Brendan McKay的nauty 2.2(最终补丁版...
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
包含多个经典的递归应用代码: 1.fibonacci.c 是斐波拉契数列递归解法 ...3.permutation.c 是全排列递归算法 4.queen.c 是八皇后递归算法 5. reverse.c 是递归的测试代码 6.strlrn.c 是求字符串长度的递归算法
1、全排列(递归) function permutation(arr){ if (arr.length == 1) return arr; else if (arr.length == 2) return [[arr[0],arr[1]],[arr[1],arr[0]]]; else { var temp = []; for (var i = 0; i < ...
全排列 VC 源代码 全排列 VC 源代码 全排列 VC 源代码
在inginious-problems-permutation/static/ui刷新js: cd permutation-task && npm install cd permutation-studio && npm install cd permutation-task && npm run-script build cd permutation-studio && npm run...
资源分类:Python库 所属语言:Python 资源全名:PermutationImportance-1.2.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
如果一个长度为n序列包含1到n的每一个数字,那么我们说这个序列是一个长度为n的全排列。现给定一个长度为n-1由U和D构成的字符串,要求你构造一个字典序最小的全排列a,使其满足: 1.若第i个字符是U,则有a[i][i+1];...
资源分类:Python库 所属语言:Python 资源全名:PermutationImportance-1.2.1.5.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
资源来自pypi官网。 资源全名:permutation_test-0.1.tar.gz
4 }while(next_permutation(a,a+n)); 下面的代码可产生1~n的全排列 #include #include using namespace std; int main(){ int n; while(scanf("%d",&n)&&n){ int a[1000]; for(int i=0;i<n;i++){ scanf(...
由于Permutation test检验计算量大而限制了其应用和推广,以致不为人熟知。现在由于计算机技术飞速发展,Permutation test又重新进入我们的视野。Permutation test有独特的优势,其对原始数据分布没有要求,特别适用...
Column permutation cipher是基于置换的加密解密方式。利用本程序可实现Column permutation cipher的加密和解密。
本文实例讲述了C++简单实现的全排列算法。分享给大家供大家参考,具体如下: #include stdafx.h #include #include #include void func(const char *str_in) { std::string str(str_in); std::sort(str.begin...