java array permutation and combination problem summary
- 2021-01-19 22:16:54
- OfStack
In the interview or written test, I have encountered the following 4 hand-tear algorithms about permutation and combination many times. Here is a note for reference of the method in the future:
1. Array without repeating elements, complete arrangement;
2. Array with repeated elements, complete arrangement;
3. Array without repeated elements, to find the combination [subset];
4. There are repeated elements of the array, find the combination;
The above 4 types of problems can be realized with the template of unified 1, as shown below:
/*
* The combination of && Arrange 】
* the 1 All combinations of numbers in the array are listed, for example 1 and 2 A list of 1,2,12,21.
* This problem can be expanded to 4 A:
*1. No duplicate number array, seek combination
*2. Have the array of duplicate numbers, find the combination
*3. No duplicate number array, complete arrangement
*4. An array of duplicate digits, complete in order
* [General idea (recursion)] :
* define 1 A function: from the candidate set candicate Select the 1 A combination of prefix
* Each time from the candidate set candicate In the remove1 Number, and add the prefix prefix To print prefix ;
* Recursion from the new candicate In the remove Under the 1 Number, and add prefix
* [Control for repetition]
* using hashset save prefix , before printing, judge hashset Contains the currently generated prefix .
* No then print and add hashset ; Some do not print
* The combination of -- "Arrange 】
* Just add it before printing 1 Judgment: if candidate set candicate Is empty, indicating that the traversal is complete 1 Time, generate 1 A permutation, printable
*/
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),"");// Initialize the 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);
}
// No duplicate combinations
public void listAllNoRepeate(List<String> candicate,String prefix){
if(prefix.length() != 0)
System.out.println(prefix);// The result length is not zero 0, The combination is printed out
for(int i = 0;i < candicate.size();i++){
// will list Converted to linklist Linked list, easy to operate
List<String> tempList = new LinkedList<String>(candicate);
//templist To reduce 1 Numbers, and temporary storage templist The number removed from
String tempString = (String) tempList.remove(i);
// recursive
listAllNoRepeate(tempList,prefix + tempString);
}
}
// There are repeated combinations , join 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);// recursive
}
}
// No repetition of the full permutation, adding judgment 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);
}
}
// There are repeated full permutations, added hashset Auxiliary judgment output
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);
}
}
}