java配列の組合せ問題のまとめ


面接や筆記試験では、次の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);
    }  
  }

  }
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。