Implementieren Sie eine Kombination aus Mathematik in Java
Vor kurzem hatte ich aus irgendeinem Grund die Möglichkeit, eine Kombination von Mathematik in Java zu implementieren. Der Code, den ich damals überprüfte, war ineffizient, deshalb habe ich ihn zu einem Artikel von Qiita gemacht.
Ich denke, Sie haben die Reihenfolge und Kombination in der Oberschulklasse gelernt, aber um zum Beispiel kurz die Anzahl der "Kombinationen, die 2 von 6 Sätzen auswählen" zu überprüfen, ist wie folgt.
【offiziell】_n \mathrm{ C }_k = \frac{n!}{k!(n-k)!} （0 < k <=(N sein)
_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
Aufgrund der Kombination bedeuten "{A, B}" und "{B, A}" dasselbe.
"Der Code war ineffizient" liegt daran, dass er öfter verarbeitet wurde als die Anzahl der Ergebnisse (15 im Beispiel). "Effizient" bedeutet, dass "die richtige Kombination mit der Mindestanzahl der erforderlichen Prozesse aufgelistet werden kann". Sie können dies sehen, indem Sie sich eine sehr große Anzahl von Sätzen vorstellen, die kombiniert werden sollen.
Ich habe versucht, den Fall der Auswahl von 2 aus der Menge von N und den Fall der Auswahl von 3 als Beispiel zu implementieren. Das Bild der Idee, die effizienteste Kombination zu suchen, ist wie folgt. Es wird davon ausgegangen, dass die Menge keine doppelten Werte enthält.
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);
}
}
Die Punkte sind die Verschachtelung sich wiederholender Schleifen sowie die Start- und Endwerte.
-
- Wiederholungsschleife: Auswahl des 1. Elements
- Zweite Wiederholungsschleife: Auswahl des zweiten Elements
- Dritte Wiederholungsschleife: Auswahl des dritten Elements (im Fall von nC3)
Wählen Sie den Startwert der verschachtelten iterativen Schleife nicht vor dem Startwert der äußeren verschachtelten Schleife aus, da Sie für die Kombination nach der Aufzählung von "{A, B}" nicht "{B, A}" auswählen müssen. ..
Ausführungsergebnis
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
Da der Wert von "num" und die Anzahl der Kombinationen gleich sind, können Sie sehen, dass die Kombination mit der minimalen Anzahl der erforderlichen Prozesse berechnet wurde.
Beim Vergleich der Erstellung von "nCombination2" und "nCombination3" hat sich nur die Anzahl der sich wiederholenden Schleifen geändert. Wenn Sie das nächste Mal versuchen, "nCombination4" hinzuzufügen, können Sie sich vorstellen, wie es aussehen würde.
Recommended Posts