Implémenter une combinaison de mathématiques en Java
Récemment, pour une raison quelconque, j'ai eu l'occasion de mettre en œuvre une combinaison de mathématiques en Java. Le code que j'ai examiné à l'époque était inefficace, alors j'en ai fait un article de Qiita.
Je pense que vous avez appris l'ordre et la combinaison dans la classe du secondaire, mais pour passer brièvement en revue, par exemple, le nombre de «combinaisons qui sélectionnent 2 sur 6 ensembles» est le suivant.
【officiel】_n \mathrm{ C }_k = \frac{n!}{k!(n-k)!} （0 < k <=(Être 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
De plus, en raison de la combinaison, «{A, B}» et «{B, A}» signifient la même chose.
"Le code était inefficace" parce qu'il traitait plus de fois que le nombre de résultats (15 dans l'exemple). «Efficace» signifie que «la combinaison correcte peut être répertoriée avec le nombre minimum de processus requis». Vous pouvez le voir en imaginant un très grand nombre d'ensembles à combiner.
J'ai essayé de mettre en œuvre le cas de la sélection de 2 dans l'ensemble de N et le cas de la sélection de 3 comme exemple. L'image de l'idée de rechercher la combinaison la plus efficace est la suivante. On suppose qu'il n'y a pas de valeurs en double dans l'ensemble.
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);
}
}
Les points sont l'imbrication des boucles répétitives et les valeurs de début et de fin.
- 1ère boucle répétée: sélection du 1er élément
- Deuxième boucle répétitive: sélection du deuxième élément
- Troisième boucle répétitive: Sélection du troisième élément (dans le cas de nC3)
Ne sélectionnez pas la valeur de départ de la boucle itérative imbriquée avant la valeur de début de la boucle imbriquée externe, car la combinaison ne vous oblige pas à sélectionner «{B, A}» après avoir énuméré «{A, B}». ..
Résultat d'exécution
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
Puisque la valeur de «num» et le nombre de combinaisons sont égaux, vous pouvez voir que la combinaison a été calculée avec le nombre minimum de processus requis.
En comparant la création de «nCombination2» et «nCombination3», seul le nombre de boucles répétitives a changé. La prochaine fois que vous essayez d'ajouter nCombination4, vous pouvez imaginer à quoi ressemblera l'implémentation.
Recommended Posts