[Java] [Java] I tried to implement a combination.

1 minute read

I tried to implement a mathematical combination in Java

I tried to implement a combination of different r out of n different ones in Java. I’ve seen an implementation that loops r number of times, I thought about various things because I wanted to be okay even if r pieces changed.

Source code

The following code is designed to take 3 out of 5.

import java.util.ArrayList;
import java.util.List;

public class Trial {

    public static void main(String[] args) {
        Trial me = new Trial();
        me.exec(args);
    }

    public void exec(String[] args) {
        // array of strings
        String[] strArray = new String[] {"a", "b", "c", "d", "e" };
        // get the combination
        String[][] combinations = getCombinations(strArray, 3);
        // result output
        for (String[] combination :combinations) {
            for (String str: combination) {
                System.out.print(" "+ str);
            }
            System.out.println();
        }
    }

    private String[][] getCombinations(String[] strArray, int selectCount) {
        // list for filling results
        List<String[]> list = new ArrayList<>();
        // Because it is used a little, keep it in a variable
        int len = strArray.length;
        // Find the maximum value in binary from the length of the array.
        int dec = 0;
        for (int i = 0; i <len; i++) {
            dec += Math.pow(2, i);
        }
        // Decrement from the maximum value.
        for (int num = dec; 0 <num; num--) {
            // Make the string in binary notation. (0 is not filled)
            String bin = Integer.toBinaryString(num);
            if (!isCombination(bin, selectCount)) {
                // Ignore if the number of 1 does not match the number of selections.
                continue;
            }
            int j = bin.length()-1;
            int tmplen = len-bin.length();
            String[] combination = new String[selectCount];
            int idx = selectCount-1;
            for (int i = len-1; tmplen <= i; i--) {
                if (bin.charAt(j--) == '1') {
                    combination[idx--] = strArray[i];
                }
            }
            list.add(combination);
        }
        return list.toArray(new String[0][0]);
    }

    private boolean isCombination(String str, int selectCount) {
        int sum = 0;
        for (int i = 0; i <str.length(); i++) {
            sum += Character.getNumericValue(str.charAt(i));
        }
        if (sum == selectCount) {
            return true;
        }
        return false;
    }
}

Execution result

  a b c
  a b d
  a b e
  a c d
  a c e
  a d e
  b c d
  b c e
  b d e
  c d e

The combination of 5 to 3 is 5! / (2! * (5-2)!) = 10 Maybe it fits.

Finally

I think there is a lot of room for improvement when it comes to performance and dealing with large numbers.

that’s all

Tags:

Updated: