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.png

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.

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

Implémenter une combinaison de mathématiques en Java
Implémentation de l'authentification en deux étapes en Java
Implémenter l'authentification de base en Java
2 Implémentez une analyse syntaxique simple en Java
Implémenter l'envoi d'e-mails en Java
Implémenter un tri rapide de type fonction en Java
Implémentez rm -rf en Java.
Implémenter la signature XML en Java
Implémenter un test piloté par table dans Java 14
Implémenter reCAPTCHA v3 dans Java / Spring
Implémenter la fonction PHP implode en Java
Essayez d'implémenter Yuma en Java
1 Implémentez une analyse de phrase simple en Java
Comment implémenter le filtre de Kalman par Java
Implémenter l'autorisation API Gateway Lambda dans Java Lambda
Partition en Java
Essayez d'implémenter l'ajout n-aire en Java
Changements dans Java 11
Janken à Java
Comment appliquer les conventions de codage en Java
Implémenter quelque chose comme une pile en Java
Taux circonférentiel à Java
FizzBuzz en Java
Lire JSON en Java
Implémentation de l'interpréteur par Java
Faites un blackjack avec Java
Application Janken en Java
Programmation par contraintes en Java
Mettez java8 dans centos7
NVL-ish guy en Java
Joindre des tableaux en Java
"Hello World" en Java
Commentaires dans la source Java
Fonctions Azure en Java
Formater XML en Java
Simple htmlspecialchars en Java
Implémentation Boyer-Moore en Java
Hello World en Java
Utiliser OpenCV avec Java
Détermination de type en Java
Exécuter des commandes en Java (ping)
Divers threads en java
Implémentation du tri de tas (en java)
API Zabbix en Java
Art ASCII à Java
Comparer des listes en Java
POST JSON en Java
Exprimer l'échec en Java
Implémenter CustomView dans le code
Créer JSON en Java
Manipulation de la date dans Java 8
Nouveautés de Java 8
[Java twig] Énumérer les combinaisons
Utiliser PreparedStatement en Java
Nouveautés de Java 9,10,11
Exécution parallèle en Java
Markdown implémenté dans Rails
J'ai essayé d'implémenter la notification push Firebase en Java