순열 (Permutation)

지인이 코딩 문제를 공유해줬는데 순열에 대한 알고리즘 문제가 있어서 다시 한번 리마인드 할 겸 글로 정리 한번 해보려고 한다.

순열 알고리즘 이란?

N개의 서로 다른 값이 주어지고  값 중에서 R개의 숫자를 뽑아서 정렬하는 알고리즘이다. 이 내용은 다른 알고리즘과 중복되긴 하는데 순열에서 중요한 건 정렬이 된다는 것이고 순서가 존재한다는 점이다.

예를 들어 [1, 2] =! [2, 1]은 다른 값이기에 둘 다 카운팅이 된다.

주어진 값 = [1, 2, 3] 이라면 순열을 하여 2개 뽑아낸 값은

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

이렇게 총 6개가 나와야 한다는 것이다.

자바 코드 구현

@Test
public void 순열() {
    int r = 2;
    int[] input = {1, 2, 3};
    int[] arr = new int[r];
    boolean[] visited = new boolean[input.length];
    permutation(input, visited, arr, 0);
}
private void permutation(int[] input, boolean[] visited, int[] arr, int index) {
    if (index == arr.length) {
        System.out.println(Arrays.toString(arr));
        return;
    }
    for (int i = 0; i < input.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            arr[index] = i + 1;
            permutation(input, visited, arr, index + 1);
            visited[i] = false;
        }
    }
}

코드 설명

- visited를 이용하여 이미 선택된 숫자를 무시하게 한다.

- visited에 선택된 숫자가 없다면 숫자에 대해 방문 표시를 하고 결과를 추출할 배열에 숫자를 저장 후 함수 재귀 호출한다.

- arr 배열에 조건의 R 개수만큼 숫자가 저장이 되었다면 함수 재귀 호출을 종료한다.

 

 

순열에 대해서 중복 값을 허용할 수 있도록 할 수 있다.

@Test
public void 순열_중복허용() {
    int r = 2;
    int[] input = {1, 2, 3};
    int[] arr = new int[r];
    permutation(input, arr, 0);
}

private void permutation(int[] input, int[] arr, int index) {
    if (index == arr.length) {
        System.out.println(Arrays.toString(arr));
        return;
    }
    for (int i = 0; i < input.length; i++) {
        arr[index] = i + 1;
        permutation(input, arr, index + 1);
    }
}

visited 배열은 중복을 걸러내기 위한 장치로 visited 배열 조건만 삭제한다면 중복도 허용된 결과를 추출해 낼 수 있다.

옆에 결과 이미지를 보면 [1., 1], [2, 2], [3, 3]을 추가 추출해 내었으므로 9개 결과가 나온다.