java配列の組合せ問題のまとめ
面接や筆記試験では、次の4つの組の手引きアルゴリズムについて、ここでメモをとります。方法は後日調べます。
1.重複要素の配列がなく、完全な配置を求める。
2.重複要素の配列があり、完全な配置を求める。
3.重複要素の配列がなく、「サブセット」を組み合わせることを求めます。
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<String> noRepeateSet = new HashSet<String>();
test.listAllRepeate(Arrays.asList(repeate), "", noRepeateSet);
System.out.println("**************no repeate premutation********************");
test.premutationNoRepeate(Arrays.asList(array),"");
System.out.println("*********************repeate premutation**********************");
HashSet<String> repeateSet = new HashSet<String>();
test.premutationRepeate(Arrays.asList(repeate),"", repeateSet);
}
//
public void listAllNoRepeate(List<String> candicate,String prefix){
if(prefix.length() != 0)
System.out.println(prefix);// 0,
for(int i = 0;i < candicate.size();i++){
// list linklist ,
List<String> tempList = new LinkedList<String>(candicate);
//templist , templist
String tempString = (String) tempList.remove(i);
//
listAllNoRepeate(tempList,prefix + tempString);
}
}
// , hashset
public void listAllRepeate(List<String> candicate,String prefix,HashSet<String> res){
if(prefix.length() != 0 && !res.contains(prefix)){
System.out.println(prefix);
res.add(prefix);
}
for(int i = 0;i < candicate.size();i++){
List<String> tempList = new LinkedList<String>(candicate);
String tempString = tempList.remove(i);
listAllRepeate(tempList, prefix+tempString, res);//
}
}
// , candicate.size() == 0
public void premutationNoRepeate(List<String> candicate,String prefix){
if(candicate.size() == 0){
System.out.println(prefix);
}
for(int i = 0;i < candicate.size();i++){
List<String> tempList = new LinkedList<String>(candicate);
String tempString = tempList.remove(i);
premutationNoRepeate(tempList,prefix+tempString);
}
}
// , hashset
public void premutationRepeate(List<String> candicate,String prefix,HashSet<String> res) {
if(candicate.size() == 0 && !res.contains(prefix)){
System.out.println(prefix);
res.add(prefix);
}
for(int i = 0;i < candicate.size();i++){
List<String> tempList = new LinkedList<String>(candicate);
String tempString = tempList.remove(i);
premutationRepeate(tempList, prefix+tempString, res);
}
}
}
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。