순열과 중복순열

알고리즘 문제를 풀면서, 매번 순열과 조합에 관한 문제가 나오면 헉!하고... 제대로 구현해보지 못한 것 같아,

이번 기회에 코드를 정리하고자 합니다.

 

순열

먼저 순열(permutation)입니다. 

순열의 정의는 "서로 다른 N개에서 R개를 뽑아서 나열한 것"입니다.

또한 이로 인해 모든 순열의 시간복잡도는 O(n!)입니다. 

 

그렇다면 순서가 상관있을까요?

맞습니다. 순서가 상관있습니다. 이 말의 의미는 다음과 같습니다.

 

숫자가 0, 1, 2로 총 3개가 있고, 이 중 2개를 뽑는 순열을 생각해봅시다.
순열은 순서가 상관있기 때문에, 즉 순서를 고려하기에, 같은 숫자를 뽑더라도 순서가 다르다면 다른 것입니다.

그렇다면 다음과 같은 순열을 얻을 수 있을 것입니다.

{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 1}

 

여기서 {0, 1} 과 {1, 0} 은 엄연히 다릅니다. 순서를 고려하기 때문입니다. 

그렇다면 이를 코드로 구현한다면 어떻게 해야 할까요 ? (매번 하는 생각입니다...)

 

먼저, 구현하는 데 있어 필요한 것들을 생각해봅시다.

우선 순열을 구하고자 하는 데이터(숫자)가 필요합니다.

다음으로는 뽑아야 하는 R개 중 현재 몇 개가 뽑혔는지, 어떤 숫자가 뽑혔는지 알아야 합니다.

(중복순열이 아니기에 본인은 제외되어야 합니다!)

 

이제 코드를 통해 알아볼텐데, 순열은 2가지(사실 1가지 더 있긴 함 - c++의 next_permutation 방식)입니다.

그중 먼저 스왑을 이용하는 코드부터 알아보겠습니다.

 

스왑을 이용한 순열

말그대로 스왑을 이용해 주어진 데이터를 직접 바꾸는 방식입니다. 

주어진 데이터의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 스왑할 때까지 반복합니다.

그리고 이러한 방식은 순열의 순서가 보장되지 않는다는 특징이 있습니다.

즉, 순열의 결과가 사전순이 아니라는 것입니다.

 

아래는 코드입니다.

public class Main {
    private static int[] array = {1,2,3,4};

    public static void main(String[] args) {
    	// 전체 데이터 개수 
        int n = array.length;
        // 데이터 중 뽑을 숫자의 개수
        int r = 3;
        
        permutation(0, n, r);
    }
	
    static void permutation(int depth, int n, int r) {
        // depth가 r과 같다면, 주어진 숫자만큼 순열을 생성했다는 의미입니다.
        if (depth == r) {
        	for (int i = 0; i < r; i++) {
            	System.out.print(array[i] + " ");
            }
            System.out.println();
            return;
        }
        
        // depth번째부터 주어진 데이터의 값을 스왑합니다.
        for (int i = depth; i < n; i++) {
            swap(depth, i);
            permutation(depth + 1, n, r);
            // 스왑하여 재귀호출한 후에는 다시 되돌려 놓습니다.
            swap(depth, i);
        }
    }
	 
    static void swap(int depth, int i) {
        int temp = arr[depth];
        array[depth] = arr[i];
        array[i] = temp;
    }
}

이러한 방식은 가끔 문제에서 스왑의 특성을 요구하는 경우가 있어 알아두는 것이 좋다고 합니다!

 

포함 여부를 확인하는 순열

이번에는 포함 여부를 확인하는 순열입니다. 

위에서 다룬 스왑을 이용하는 방식보다 직관적이고, 추가적인 로직을 수행할 수 있습니다.

그리고 스왑을 이용하는 방식과 달리 순열의 결과가 사전순임이 보장됩니다.

 

아래는 코드입니다.

public class Main {
    static int[] array = {1,2,3,4};

    public static void main(String[] args) {
    	// 전체 데이터 개수
        int n = array.length;
        // 데이터 중 뽑을 숫자의 개수
        int r = 3;
        
        permutation(new int[n], new boolean[n], 0, n, r);
    }

    static void permutation(int[] output, boolean[] visited, int depth, int n, int r) {
        // depth == r라면, 순열이 완성되었음을 의미합니다.
        if (depth == r) {
            // 따라서 완성된 순열을 출력하고 돌아갑니다.
            // 이를 응용하여, 순열이 완성된 경우 특정 로직을 수행할 수 있습니다.
            for (int i = 0; i < r; i++) {
            	System.out.print(output[i] + " ");
            }
            System.out.println();
            return;
        }
        
        // 여기서는 주어진 숫자(데이터)를 탐색하면서, 이미 순열에 포함되지 않은 숫자를 임시 순열 배열에 넣고,
        // 다음 숫자를 추가할 수 있도록 본 함수를 재귀호출합니다.
        for (int i = 0; i < n; i++) {
        	if (visited[i]) {
            	continue;
            }
            // 해당 인덱스의 숫자가 아직 순열에 없다면, 추가할 수 있습니다.
            // 해당 숫자를 순열에 포함했음을 표시하고,
            visited[i] = true;
            // 임시 순열 배열에 숫자를 추가합니다.
            output[depth] = array[i];
            // 그리고 depth를 1 증가시켜 다음 숫자를 추가할 수 있도록 재귀호출합니다.
            permutation(output, visited, depth + 1, n, r);
            // 재귀가 끝난 후에는 해당 자리에 다른 숫자를 추가할 수 있도록 비워줍니다.
            // 사실 이 과정은 필요없습니다. 어차피 다른 숫자가 쓰여질 것이기 때문입니다.
            output[depth] = 0;
            // 그리고 해당 숫자가 순열에 포함되지 않았음을 표시합니다.
            visited[i] = false;
        }
    }
}

• arr 는 순열을 뽑을 데이터입니다.
• n과 r은 각각 전체 데이터 개수와 순열로 뽑을 개수를 의미합니다.
• output은 임시 순열 저장소입니다. 순열이 완성되었다면, 해당 배열에 완성된 순열이 존재할 것입니다.
• visited는 해당 인덱스의 데이터가 이미 순열에 포함되었는지 여부를 저장합니다.
• depth는 현재 몇 개의 데이터가 순열에 포함되었는지를 의미합니다.

 

현재는 배열을 사용해 순열을 구현하였는데, List<T>를 이용해서도 구현이 가능합니다. 아래와 같은 코드일 것입니다.

 

static void permutation(List<Integer> output, boolean[] visited, int n, int r) {
    if (output.size() == r) {
        for (int out : output) {
        	System.out.print(out + " ");
        }
        System.out.println();
        return;
    }
    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            continue;
        }
        output.add(array[i]);
        visited[i] = true;
        perm(output, visited, n, r);
        visited[i] = false;
        output.remove(output.size() - 1);
    }
}

---

중복순열

다음은 중복순열입니다. 이름에 순열이 들어가니, 순열과 같은 특성을 가지면서 "중복"을 허용한다는 말일 듯합니다.

여기서 허용하는 중복은 자기 자신을 의미합니다.

따라서 위의 예제를 가져와 중복순열을 구한다면, 다음과 같이 얻을 수 있습니다.

{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}

 

이를 구현하려면, 무엇이 필요할까요?

중복이라는 말이 붙으면서, 순열에 포함했던 숫자를 다시 사용할 수 있게 되었습니다.

하지만 여전히 순열을 구해야하는 것은 동일하기에,

어떤 숫자가 뽑혔는지를 저장할 필요는 없어졌습니다.

 

바로 코드로 넘어가보겠습니다. (큰 차이가 없기에 List<T>를 사용하는 코드를 사용했습니다.)

 

public class Main {
    static int[] array = {1,2,3,4};

    public static void main(String[] args) {
        // 전체 데이터 개수 
        int n = arr.length;
        // 데이터 중 뽑을 숫자의 개수
        int r = 3;

        permutation(new ArrayList<>(), n, r);
    }
	
    static void permutation(List<Integer> output, int n, int r) {
        if (output.size() == r) {
            for (int out : output) {
            	System.out.print(out + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            output.add(array[i]);
            permutation(output, n, r);
            output.remove(output.size() - 1);
        }
    }
}

기존 순열 코드에서 포함여부를 확인하는 로직만 제거된 것을 확인할 수 있습니다.

 

---

본 포스트에서 순열과 중복순열에 대해 정리했습니다.

다음 시간에는 조합과 중복조합에 대해 정리해보도록 하겠습니다!

 

참고

https://bcp0109.tistory.com/14

순열 Permutation (Java)

https://velog.io/@junhok82/Java%EB%A1%9C-%EC%88%9C%EC%97%B4Permutation-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0#next_permutation

Java로 순열(Permutation) 구현하기

https://limkydev.tistory.com/178

[JAVA] 조합,중복조합,순열,중복순열 소스