/*
 *【組合&&排列】
 *把一個數(shù)組里的數(shù)組合全部列出，比如1和2列出來為1,2,12,21.
 *這個題目可以擴(kuò)展成四個：
 *1.無重復(fù)數(shù)字的數(shù)組，求組合
 *2.有重復(fù)數(shù)字的數(shù)組，求組合
 *3.無重復(fù)數(shù)字的數(shù)組，求全排列
 *4.有重復(fù)數(shù)字的數(shù)組，求全排列
 *【通用思路（遞歸）】：
 *定義一個函數(shù)：從候選集candicate中選取一個組合prefix
 *每次從候選集candicate中remove一個數(shù)，并加入前綴prefix，打印prefix；
 *再遞歸從新的candicate中remove下一個數(shù)，并加入prefix
 *【對于重復(fù)的控制】
 *采用hashset保存prefix，打印之前，判斷hashset中是否包含當(dāng)前生成的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);
  }
  //無重復(fù)的組合
  public void listAllNoRepeate(List<String> candicate,String prefix){ 
    if(prefix.length() != 0)
      System.out.println(prefix);//結(jié)果長度不為0,則打印輸出該組合

    for(int i = 0;i < candicate.size();i++){
      //將list轉(zhuǎn)換成linklist鏈表，方便操作
      List<String> tempList = new LinkedList<String>(candicate);
      //templist減少一個數(shù)字，并暫存templist中去除的數(shù)字
      String tempString = (String) tempList.remove(i);
      //遞歸
      listAllNoRepeate(tempList,prefix + tempString);
    }
  }

  //有重復(fù)的組合,加入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);//遞歸
    }
  }

  //無重復(fù)的全排列，加入判斷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);
    }
  }

  //有重復(fù)的全排列，加入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);
    }  
  }

  }