I only write a combination algorithm here.
Suppose that there are M=4 data a, b, c, d. From this, n numbers are randomly selected, and n is 1-4 data for combination. Then the calculation combination method in mathematics is C(4,1) + C(4,2) + C(4,3) + C(4,4) = 4 + 6 + 4 + 1 = 15. There are 15 combinations in total.
Solution 1: This method is easy to understand but slow to achieve
My approach is to cyclically combine the data in order, and the data is divided into combined data and uncombined (uncombined data refers to the remaining data in the future). Then, the uncombined data are combined again with the combined, and the loop is carried out until the end.
The following example, rules
Combined data Remaining data that has not participated in the combination
1 a
2 b
3 c
4 d
//Start the second loop combination of line 1 a - b, c, d above
5 a,b
6 a,c d
7 a,d
//Start loop combination of lines a, b — c, d above 5
8 a,b,c //a,b,c There is still d afterwards that has not participated
9 a,b,c,d
//Start loop combination of lines b - c,d above
10 b,c //b,c There is still c,d afterwards without participation
11 b,d
//Start loop combination of line c — d above
12 c,d
//Start loop combination of lines a, c — d above
13 a,c,d
//Start loop combination of lines a, b, c — d on the above 8
14 a,b,c,d
//Start loop combination of lines b, c - d above
15 b,c,d
..................... According to the above rules, the uncombined rows are combined with the currently combined ones again, and then the remaining uncombined data is calculated. The number of data not participating in the combination is 0
The above idea is basically clear. Combine in sequence, just based on the uncombined data on each row, and then combine again until all combinations are completed. The code implementation is as follows:
public static void main(String[] args) {
//Result Set List<String> resList = new ArrayList<>();
//Initialize the data that needs to be combined String[] arr = new String[]{"a","b","c","d"};
List<String> initList = new LinkedList((arr));
//Map key: prefix of combined data, value: data not participating in combination Map<String,List<String>> map = new HashMap<>();
for (int i = 0; i < (); i++) {
String pj = (i);
(pj);
(pj);
//When the remaining uncombined data is 0, no further addition if(i+1 < ()){
//Sorted in order Subscript is data that has not participated in the combination after i List<String> syList = (i+1,());
(pj,syList);
}
}
combinLoop(map,resList);
(());
}
public static void combinLoop(Map<String,List<String>> map,List<String> resList){
for (<String, List<String>> entry : ()) {
String prefix = ();
List<String> list = ();
Map<String,List<String>> map2 = new HashMap<>();
// Loop the data that is not involved in the combination and combine it with the previous prefix for (int i = 0; i < (); i++) {
String newPre = prefix+(i);
(newPre);
(newPre);
if(i+1 < ()){
//Sorted in order, the subscript is a data set that is not participated in the combination after i. List<String> syList = (i+1,());
(newPre,syList);
}
}
combinLoop(map2,resList);
}
}Solution 2: Faster efficiency
In this method, loops the initialized data initList, combines the previous result resultList with the current data participating in the loop one by one, obtains new results added to the existing combination result resultList, initList loops in turn, resultList continues to add new data, and repeats until the end. The following example:
Loop on initList = {"a","b","c","d"} and initialize resultList to empty.
Current participation in loop data Previous resultList set End resultList set
First loop
The second loop
The third loop
The fourth loop a,b,ab,c,ac,bc,ac,bc,abc,d,ad,bd,abd,cd,acd,bcd,acd,bcd,abcd
From the above rules, we can see that if the data participating in the loop is combined with the existing resultList set, the result after the yellow part is combined can be obtained. Add the original data in the resultList to form a new resultList and the data participating in the next loop, and then proceed in sequence until all data loops are completed.
The code is as follows:
public static void combine2(){
String[] arr = new String[]{"a","b","c","d"};
//Initialize the data List<String> initList = (arr);
//Result Set List<String> resultList = new ArrayList<>();
for (String init : initList) {
//Reassign the resultList result set obtained after the last loop combination List<String> list = new ArrayList<>(resultList);
//resultList adds initial data (init);
for (String pr : list) {
//Recombined the resultList obtained in the previous time with the current data (pr + init);
}
}
}This is the end of this article about the two solutions for Java implementing the arrangement and combination algorithm. For more related contents of Java arrangement and combination algorithm, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!