[JAVA] 순열(Permutation), 조합(Combination) 알고리즘

 

순열(Permutation)

 서로 다른 n개의 원소에서 r개를 순서를 고려하여 선택하는 것이다. 아래는 백트래킹으로 3개 중 3개를 선택하는 순열을 구하는 자바 코드이다.

import java.io.*;
import java.util.*;

public class Main {
    static List<List<Integer>> results = new ArrayList<>();
    static List<Integer> list = new ArrayList<>();
    static int[] input;
    static int n, r;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input = new int[]{1, 2, 3};
        n = input.length;
        r = 3;
        visited = new boolean[n];

        permutation(0);

        for (List<Integer> result : results) {
            for (int num : result) {
                bw.write(num + " ");
            }
            bw.write("\n");
        }
        bw.flush();
    }

    public static void permutation(int depth) {
        if (depth == r) {
            results.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }

            visited[i] = true;
            list.add(input[i]);
            permutation(depth + 1);
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

// Output
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

 

조합(Combination)

 서로 다른 n개의 원소에서 r개를 중복 없이, 순서를 고려하지 않고 선택하는 것이다. 아래는 백트래킹으로 3개 중 2개를 션택하는 조합을 구하는 자바 코드이다.

import java.io.*;
import java.util.*;

public class Main {
    static List<List<Integer>> results = new ArrayList<>();
    static List<Integer> list = new ArrayList<>();
    static int[] input;
    static int n, r;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input = new int[]{1, 2, 3};
        n = input.length;
        r = 2;

        combination(0, 0);

        for (List<Integer> result : results) {
            for (int num : result) {
                bw.write(num + " ");
            }
            bw.write("\n");
        }
        bw.flush();
    }

    public static void combination(int depth, int start) {
        if (depth == r) {
            results.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < n; i++) {
            list.add(input[i]);
            combination(depth + 1, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

// Output
1 2 
1 3 
2 3

 

...
static Map<String, Integer> combiMap = new HashMap<>();
...

...
public void combi(int idx, int r, char[] arr, StringBuilder sb) {
    if (sb.length() == r) {
        combiMap.put(sb.toString(), combiMap.getOrDefault(sb.toString(), 0) + 1);
        return;
    }

    for (int i = idx; i < arr.length; i++) {
        sb.append(arr[i]);
        combi(i + 1, r, arr, sb);
        sb.deleteCharAt(sb.length() - 1); // 백트래킹
    }
}