[GO] Implement math combinations in Java
Recently, for some reason, I had the opportunity to implement math combinations in Java. The code I reviewed at that time was inefficient, so I made it an article on Qiita.
I think you learned permutations and combinations in high school classes, but to briefly review, for example, the number of "combinations that select 2 out of 6 sets" is as follows.
【official】_n \mathrm{ C }_k = \frac{n!}{k!(n-k)!} （0 < k <=(Being n)
_6 \mathrm{ C }_2 = \frac{6!}{2!(6-2)!} = \frac{6!}{2!\times4!} = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{2 \times 1 \times 4 \times 3 \times 2 \times 1} = \frac{6 \times 5 }{2 \times 1} = 15
Also, as a result of the combination, {A, B} and {B, A} mean the same thing.
"The code was inefficient" is because it was processing more times than the number of results (15 in the example). "Efficient" means that "the correct combination can be listed with the minimum number of processes required". You can see this by imagining a very large number of sets to be combined.
I implemented the case of selecting 2 from the set of N and the case of selecting 3 as an example. The image of the idea of seeking the most efficient combination is as follows. It is assumed that there are no duplicate values in the set.
Combination.java
package com.example.demo;
public class Combination {
public static void main(String[] args) {
String[] list = { "A", "B", "C", "D", "E", "F"};
nCombination2(list);
nCombination3(list);
String[] list2 = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
nCombination2(list2);
nCombination3(list2);
}
private static void nCombination2(String[] list) {
int count = list.length;
int num = 0;
for (int i = 0; i < count - 1; i++) {
for (int j = i + 1; j < count; j++) {
num++;
System.out.print(num + " {" + list[i] + ", " + list[j] + "}\t");
}
System.out.println();
}
System.out.println("[answer] " + count + "C2 : " + num);
}
private static void nCombination3(String[] list) {
int count = list.length;
int num = 0;
for (int i = 0; i < count - 2; i++) {
for (int j = i + 1; j < count - 1; j++) {
for (int k = j + 1; k < count; k++) {
num++;
System.out.print(num + " {" + list[i] + ", " + list[j] + ", " + list[k] + "}\t");
}
}
System.out.println();
}
System.out.println("[answer] " + count + "C3 : " + num);
}
}
The points are the nesting of repeating loops and the start and end values.
- First repeating loop: Selection of the first element
- Second repeating loop: Selection of the second element
- Third repeating loop: Selection of the third element (in the case of nC3)
Do not select the start value of a nested iterative loop before the start value of an outer nested loop, as the combination does not require you to select {B, A} after enumerating {A, B}. ..
Execution result
1 {A, B} 2 {A, C} 3 {A, D} 4 {A, E} 5 {A, F}
6 {B, C} 7 {B, D} 8 {B, E} 9 {B, F}
10 {C, D} 11 {C, E} 12 {C, F}
13 {D, E} 14 {D, F}
15 {E, F}
[answer] 6C2 : 15
1 {A, B, C} 2 {A, B, D} 3 {A, B, E} 4 {A, B, F} 5 {A, C, D} 6 {A, C, E} 7 {A, C, F} 8 {A, D, E} 9 {A, D, F} 10 {A, E, F}
11 {B, C, D} 12 {B, C, E} 13 {B, C, F} 14 {B, D, E} 15 {B, D, F} 16 {B, E, F}
17 {C, D, E} 18 {C, D, F} 19 {C, E, F}
20 {D, E, F}
[answer] 6C3 : 20
1 {A, B} 2 {A, C} 3 {A, D} 4 {A, E} 5 {A, F} 6 {A, G} 7 {A, H} 8 {A, I} 9 {A, J}
10 {B, C} 11 {B, D} 12 {B, E} 13 {B, F} 14 {B, G} 15 {B, H} 16 {B, I} 17 {B, J}
18 {C, D} 19 {C, E} 20 {C, F} 21 {C, G} 22 {C, H} 23 {C, I} 24 {C, J}
25 {D, E} 26 {D, F} 27 {D, G} 28 {D, H} 29 {D, I} 30 {D, J}
31 {E, F} 32 {E, G} 33 {E, H} 34 {E, I} 35 {E, J}
36 {F, G} 37 {F, H} 38 {F, I} 39 {F, J}
40 {G, H} 41 {G, I} 42 {G, J}
43 {H, I} 44 {H, J}
45 {I, J}
[answer] 10C2 : 45
1 {A, B, C} 2 {A, B, D} 3 {A, B, E} 4 {A, B, F} 5 {A, B, G} 6 {A, B, H} 7 {A, B, I} 8 {A, B, J} 9 {A, C, D} 10 {A, C, E} 11 {A, C, F} 12 {A, C, G} 13 {A, C, H} 14 {A, C, I} 15 {A, C, J} 16 {A, D, E} 17 {A, D, F} 18 {A, D, G} 19 {A, D, H} 20 {A, D, I} 21 {A, D, J} 22 {A, E, F} 23 {A, E, G} 24 {A, E, H} 25 {A, E, I} 26 {A, E, J} 27 {A, F, G} 28 {A, F, H} 29 {A, F, I} 30 {A, F, J} 31 {A, G, H} 32 {A, G, I} 33 {A, G, J} 34 {A, H, I} 35 {A, H, J} 36 {A, I, J}
37 {B, C, D} 38 {B, C, E} 39 {B, C, F} 40 {B, C, G} 41 {B, C, H} 42 {B, C, I} 43 {B, C, J} 44 {B, D, E} 45 {B, D, F} 46 {B, D, G} 47 {B, D, H} 48 {B, D, I} 49 {B, D, J} 50 {B, E, F} 51 {B, E, G} 52 {B, E, H} 53 {B, E, I} 54 {B, E, J} 55 {B, F, G} 56 {B, F, H} 57 {B, F, I} 58 {B, F, J} 59 {B, G, H} 60 {B, G, I} 61 {B, G, J} 62 {B, H, I} 63 {B, H, J} 64 {B, I, J}
65 {C, D, E} 66 {C, D, F} 67 {C, D, G} 68 {C, D, H} 69 {C, D, I} 70 {C, D, J} 71 {C, E, F} 72 {C, E, G} 73 {C, E, H} 74 {C, E, I} 75 {C, E, J} 76 {C, F, G} 77 {C, F, H} 78 {C, F, I} 79 {C, F, J} 80 {C, G, H} 81 {C, G, I} 82 {C, G, J} 83 {C, H, I} 84 {C, H, J} 85 {C, I, J}
86 {D, E, F} 87 {D, E, G} 88 {D, E, H} 89 {D, E, I} 90 {D, E, J} 91 {D, F, G} 92 {D, F, H} 93 {D, F, I} 94 {D, F, J} 95 {D, G, H} 96 {D, G, I} 97 {D, G, J} 98 {D, H, I} 99 {D, H, J} 100 {D, I, J}
101 {E, F, G} 102 {E, F, H} 103 {E, F, I} 104 {E, F, J} 105 {E, G, H} 106 {E, G, I} 107 {E, G, J} 108 {E, H, I} 109 {E, H, J} 110 {E, I, J}
111 {F, G, H} 112 {F, G, I} 113 {F, G, J} 114 {F, H, I} 115 {F, H, J} 116 {F, I, J}
117 {G, H, I} 118 {G, H, J} 119 {G, I, J}
120 {H, I, J}
[answer] 10C3 : 120
Since the value of num and the number of combinations are equal, you can see that the combination was requested with the minimum number of processes required.
Comparing the creation of nCombination2 and nCombination3, only the number of repeating loops has changed. The next time you try to add nCombination4, you can imagine what the implementation will look like.
Recommended Posts