전체 소스코드

순열

순열이란 n개중 r개를 순서를 가지고 선택하는 방법의 수를 의미한다. 즉, (1,2)와 (2,1)이 다른 경우이다.

자바에서는 해당 코드를 구현하기 위해 swap을 통해 첫번째 값부터 고정시켜가며 구한다.

코드

import java.util.ArrayList;

class Permutation {
    private final int n;
    private final int r;
    private final int[] now;
    private final ArrayList<ArrayList<Integer>> result;

    /**
     * nPr에 n과 r 이다.
     * @param n 대상의 수
     * @param r 선택할 수
     */
    public Permutation(int n, int r) {
        this.n = n;
        this.r = r;
        this.now = new int[r];
        this.result = new ArrayList<>();
    }

    public void swap(ArrayList<Integer> arr, int i, int j) {
        int temp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, temp);
    }

    /**
     * swap하여 앞에서부터 하나씩 고정시켜 개수를 구함
     * @param arr 대상
     * @param depth 현재 선택된 수
     */
    public void permutation(ArrayList<Integer> arr, int depth) {
        // 원하는 개수에 도달하면 결과에 저장
        if (depth == r) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(now[i]);
            }
            result.add(temp);
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            now[depth] = arr.get(depth);
            permutation(arr, depth + 1);
            swap(arr, i, depth);
        }
    }

}

테스트 결과

• 500개중 3개 선택: 실패
• 300개중 3개 선택: 3354ms
• 100개중 3개 선택: 189ms

조합

순서의 관계없이 n개중 r개를 선택하는 경우의 수를 구하는 것이다. 여기선 (1,2)와 (2,1)이 같다.

선택대상이 되는 배열의 앞에서부터 하나씩 선택하거나 선택하지 않는 방법으로 진행해나간다.

코드

public class Combination {
    private final int n;
    private final int r;
    private final int[] now;
    private final ArrayList<ArrayList<Integer>> result;


    /**
     * nCr에 n과 r 이다.
     * @param n 대상 수
     * @param r 선택할 수
     */
    public Combination(int n, int r) {
        this.n = n;
        this.r = r;
        this.now = new int[r];
        this.result = new ArrayList<>();
    }


    /**
     * 앞에서부터 순서대로 해당 index의 값을 포함하거나 포함하지 않는 방식으로 구한다.
     * @param arr 원하는 값
     * @param depth 현재 세어진 개수(무조건 0 넣기)
     * @param index 현재까지 도달한 index
     * @param target 앞에서부터 진행된 수(더이상 값이 없는 끝에 도달하면 멈추기 위함)
     */
    public void combination(ArrayList<Integer> arr, int depth, int index, int target) {
        // nCr에서 r에 도달하면 원하는 결과이므로 추가
        if (depth == r) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(arr.get(now[i]));
            }
            result.add(temp);
            return;
        }
        // 끝까지 도달하면 그냥 리턴
        if (target == n) {
            return;
        }
        now[index] = target;
        // 해당 인덱스를 포함하는 조합
        combination(arr, depth + 1, index + 1, target + 1);
        // 해당 인덱스를 포함하지 않는 조합
        combination(arr, depth, index, target + 1);
    }


}

결과

• 500개중 3개 선택: 1810ms
• 100개중 3개 선택: 34ms

확실히 순열보다 빠르다.

파이썬에서의 순열 조합

파이썬에서는 순열, 조합을 itertools라는 기본 라이브러리에서 제공한다.

import itertools

data = [1, 2, 3, 4, 5]

# 순열(ex. 5C2)
for x in itertools.permutations(data, 2):
    print(list(x), end=' ')
 
# 조합(ex. 5P2)
for x in itertools.combinations(data, 2):
    print(list(x), end=' ')

파이썬이 코딩테스트로는 역시 꿀인것 같다.🤯