[JAVA] 순열과 조합 구현하기

 

요즘 코테 공부하면서 순열, 조합을 구현할 일이 많은데 자꾸 까먹어서 정리한다. 특히 백트래킹 문제에서 거의 필수적으로 등장하는 것 같다.

구글링 하면서 제일 직관적이고 이해가 쉽다고 느꼈던 링크를 참고해서 작성한다!

순열
  - nPr (서로 다른 n개 중 r개를 선택하는 경우의 수. 순서 상관 있음.)
  - (1,2) 와 (2,1) 을 서로 다른 것으로 취급한다.
조합
  - nCr (서로 다른 n개 중 r개를 선택하는 경우의 수. 순서 상관 없음.)
  - (1,2) 와 (2,1) 을 서로 같은 것으로 취급한다.

 

순열, 조합 모두 재귀로 구현한다.

n개 중 r개를 뽑아서 output 배열에 저장할 것이다. 이때, 순열은 순서가 상관 있으므로 방문 배열(visited)를 추가로 선언해주어야 한다.

 

 

순열

1) 뽑은 숫자들을 ouput 배열에 저장하여 바로 출력해내는 코드이다.

import java.util.*;
public class Main {
    public static int[] output;
    public static int n,r;
    public static boolean[] visited;
    public static void main(String[] args) {
        n = 3;
        r = 2;
        output = new int[r];
        visited = new boolean[n];

        perm(0);
    }
    public static void perm(int cnt){
        if(cnt == r){   // 선택한 숫자가 r개가 되면 return
            System.out.println(Arrays.toString(output));
            return;
        }
        for (int i = 0; i < n; i++) {
            if(visited[i]){
                continue;
            }
            output[cnt] = i;
            visited[i] = true;
            perm(cnt + 1);
            visited[i] = false;
        }
    }
}

 

[0, 1]
[0, 2]
[1, 0]
[1, 2]
[2, 0]
[2, 1]

 

 

2) 뽑은 숫자들을 permSet 리스트에 저장해 두었다가 마지막에 한번에 출력하는 코드이다.

import java.util.*;

public class Main {
    public static int[] output;
    public static ArrayList<int[]> permSet;
    public static int n, r;
    public static boolean[] visited;

    public static void main(String[] args) {
        n = 3;
        r = 2;
        output = new int[r];
        permSet = new ArrayList<>();
        visited = new boolean[n];

        perm(0);
        for (int i = 0; i < permSet.size(); i++) {
            System.out.println(Arrays.toString(permSet.get(i)));
        }
    }

    public static void perm(int cnt) {
        if (cnt == r) {   // 선택한 숫자가 r개가 되면 return
            permSet.add(new int[] {output[0], output[1]});
            return;
        }
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }
            output[cnt] = i;
            visited[i] = true;
            perm(cnt + 1);
            visited[i] = false;
        }
    }
}

[0, 1]
[0, 2]
[1, 0]
[1, 2]
[2, 0]
[2, 1]

 

 

조합

조합은 현재 선택한 숫자의 다음 위치의 숫자를 추가적으로 선택하게 된다. 따라서, 함수의 인자로 시작 인덱스 값을 추가해주어야 한다.

 

1) 뽑은 숫자들을 ouput 배열에 저장하여 바로 출력해내는 코드이다.

import java.util.*;

public class Main {
    static int[] output;
    static int n, r;

    public static void main(String[] args) {
        n = 3;
        r = 2;
        output = new int[r];
        combi(0,0);
    }
    public static void combi(int cnt, int start) {
        if (cnt == r) {
            System.out.println(Arrays.toString(output));
            return;
        }
        for (int i = start; i < n; i++) {
            output[cnt] = i;
            combi(cnt+1, i+1);
        }
    }
}

[0, 1]
[0, 2]
[1, 2]

 

 

2) 뽑은 숫자들을 combiSet 리스트에 저장해 두었다가 마지막에 한번에 출력하는 코드이다.

import java.util.*;

public class temp {
    static int[] output;
    static ArrayList<int[]> combiSet;
    static int n, r;

    public static void main(String[] args) {
        n = 3;
        r = 2;
        output = new int[r];
        combiSet = new ArrayList<>();
        combi(0,0);
        for (int i = 0; i < combiSet.size(); i++) {
            System.out.println(Arrays.toString(combiSet.get(i)));
        }
    }
    public static void combi(int cnt, int start) {
        if (cnt == r) {
            combiSet.add(new int[] {output[0], output[1]});
            return;
        }
        for (int i = start; i < n; i++) {
            output[cnt] = i;
            combi(cnt+1, i+1);
        }
    }
}

[0, 1]
[0, 2]
[1, 2]

 

 

 

 

Reference

https://velog.io/@jiwon_choi/%EC%9E%90%EB%B0%94%EC%97%90%EC%84%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-e0utv9d4

자바에서 순열과 조합