java中数组排列组合问题的示例分析
这篇文章主要介绍了java中数组排列组合问题的示例分析，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
龙泉网站制作公司哪家好，找成都创新互联公司！从网页设计、网站建设、微信开发、APP开发、响应式网站建设等网站项目制作，到程序开发，运营维护。成都创新互联公司2013年开创至今到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联公司。
面试或笔试中，多次遇到以下4个关于排列组合的手撕算法，这里做个笔记，方法日后查阅：
1. 无重复元素的数组，求全排列；
2. 有重复元素的数组，求全排列；
3. 无重复元素的数组，求组合【子集】；
4. 有重复元素的数组，求组合；
以上四类题，可以用统一的模板实现，如下所示：
/*
*【组合&&排列】
*把一个数组里的数组合全部列出，比如1和2列出来为1,2,12,21.
*这个题目可以扩展成四个：
*1.无重复数字的数组，求组合
*2.有重复数字的数组，求组合
*3.无重复数字的数组，求全排列
*4.有重复数字的数组，求全排列
*【通用思路（递归）】：
*定义一个函数：从候选集candicate中选取一个组合prefix
*每次从候选集candicate中remove一个数，并加入前缀prefix，打印prefix；
*再递归从新的candicate中remove下一个数，并加入prefix
*【对于重复的控制】
*采用hashset保存prefix，打印之前，判断hashset中是否包含当前生成的prefix，
*没有则打印，并加入hashset；有则不打印
*【组合--》排列】
*只需在打印前加一个判断：若候选集candicate为空，表示遍历完一次，生成一个排列，可打印
*/
package xh.offer.practice;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
public class listAllGroup{
public static void main(String[] args) {
String [] array = {"1","2"};
String [] repeate = {"1","2","1"};
listAllGroup test = new listAllGroup();
System.out.println("**********no repeate list*******");
test.listAllNoRepeate(Arrays.asList(array),"");//初始化prefix = ""
System.out.println("**********repeate list*******");
HashSet noRepeateSet = new HashSet();
test.listAllRepeate(Arrays.asList(repeate), "", noRepeateSet);
System.out.println("**************no repeate premutation********************");
test.premutationNoRepeate(Arrays.asList(array),"");
System.out.println("*********************repeate premutation**********************");
HashSet repeateSet = new HashSet();
test.premutationRepeate(Arrays.asList(repeate),"", repeateSet);
}
//无重复的组合
public void listAllNoRepeate(List candicate,String prefix){
if(prefix.length() != 0)
System.out.println(prefix);//结果长度不为0,则打印输出该组合
for(int i = 0;i < candicate.size();i++){
//将list转换成linklist链表，方便操作
List tempList = new LinkedList(candicate);
//templist减少一个数字，并暂存templist中去除的数字
String tempString = (String) tempList.remove(i);
//递归
listAllNoRepeate(tempList,prefix + tempString);
}
}
//有重复的组合,加入hashset
public void listAllRepeate(List candicate,String prefix,HashSet res){
if(prefix.length() != 0 && !res.contains(prefix)){
System.out.println(prefix);
res.add(prefix);
}
for(int i = 0;i < candicate.size();i++){
List tempList = new LinkedList(candicate);
String tempString = tempList.remove(i);
listAllRepeate(tempList, prefix+tempString, res);//递归
}
}
//无重复的全排列，加入判断candicate.size() == 0
public void premutationNoRepeate(List candicate,String prefix){
if(candicate.size() == 0){
System.out.println(prefix);
}
for(int i = 0;i < candicate.size();i++){
List tempList = new LinkedList(candicate);
String tempString = tempList.remove(i);
premutationNoRepeate(tempList,prefix+tempString);
}
}
//有重复的全排列，加入hashset辅助判断输出
public void premutationRepeate(List candicate,String prefix,HashSet res) {
if(candicate.size() == 0 && !res.contains(prefix)){
System.out.println(prefix);
res.add(prefix);
}
for(int i = 0;i < candicate.size();i++){
List tempList = new LinkedList(candicate);
String tempString = tempList.remove(i);
premutationRepeate(tempList, prefix+tempString, res);
}
}
} 感谢你能够认真阅读完这篇文章，希望小编分享的“java中数组排列组合问题的示例分析”这篇文章对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，更多相关知识等着你来学习!
网页标题：java中数组排列组合问题的示例分析
文章转载：http://cdiso.cn/article/jeohih.html
