[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.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);
    }
}

The points are the nesting of repeating loops and the start and end values.

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

Implement math combinations in Java
Implement two-step verification in Java
Implement Basic authentication in Java
2 Implement simple parsing in Java
Implement Email Sending in Java
Implement functional quicksort in Java
Implement rm -rf in Java.
Implement XML signature in Java
Implement Table Driven Test in Java 14
Implement reCAPTCHA v3 in Java / Spring
Implement PHP implode function in Java
Try to implement Yubaba in Java
1 Implement simple lexical analysis in Java
How to implement Kalman filter in Java
Implement API Gateway Lambda Authorizer in Java Lambda
Partization in Java
Try to implement n-ary addition in Java
Changes in Java 11
Rock-paper-scissors in Java
How to implement coding conventions in Java
Implement something like a stack in Java
Pi in Java
FizzBuzz in Java
I tried to implement deep learning in Java
[java] sort in list
Read JSON in Java
Interpreter implementation in Java
Make Blackjack in Java
Rock-paper-scissors app in Java
Constraint programming in Java
Put java8 in centos7
NVL-ish guy in Java
Combine arrays in Java
"Hello World" in Java
Comments in Java source
Azure functions in java
Format XML in Java
Simple htmlspecialchars in Java
Boyer-Moore implementation in Java
Hello World in Java
Use OpenCV in Java
Type determination in Java
Ping commands in Java
Various threads in java
Heapsort implementation (in java)
Zabbix API in Java
ASCII art in Java
Compare Lists in Java
POST JSON in Java
Express failure in Java
Implement CustomView in code
Create JSON in Java
Date manipulation in Java 8
What's new in Java 8
[Java twigs] Enumerate combinations
Use PreparedStatement in Java
What's new in Java 9,10,11
Parallel execution in Java
Initializing HashMap in Java
Implement markdown in Rails
I tried to implement Firebase push notification in Java