재귀함수로 Permutation 구하기 (Recursive Permutation)

 

 

- 목차

 

소개.

재귀함수로 Permutation 을 구하는 방법과 아이디어에 대해서 작성해보려고 합니다.

Permutation 은 우리말로 순열이라고 하구요. 순서를 고려하는 모든 경우의 수를 의미합니다.

예를 들어, 수열 1,2,3,4 가 존재하고 수열 1,2,3,4 로 표현할 수 있는 모든 경우의 수는 아래와 같습니다.

 

 1234 1243 1324 1342 1423 1432 
 2134 2143 2314 2341 2413 2431
 3124 3142 3214 3241 3412 3421 
 4123 4132 4213 4231 4312 4321

 

해당하는 수열을 구하는 아이디어와 방식들에 대해서 알아보려고 합니다.

 

재귀함수를 통한 구현.

4개의 대상을 나열하는 모든 경우의 수를 재귀함수로 표현할 수 있습니다.

 

아이디어는 다음과 같습니다.

 

수열 1,2,3,4 로 표현되는 순열의 케이스가 많다보니 일부만 발췌하였습니다.

1,2,3,4 의 모든 순열을 재귀방식으로 추출하기 위해서 위와 같은 방식으로 탐색이 수행됩니다.

처음 상태인 seq 는 1, 2, 3, 4 를 가집니다.

그리고 다음 단계에서 (2,3,4) , (1,3,4), (1,2,4), (1,2,3) 으로 분리됩니다.

그리고 그 다음 단계 또한 (3,4), (2,4) ... 으로 분리가 되는데요.

이러한 방식으로 seq 가 Empty 상태가 될 때까지 반복합니다.

이렇게 되면 seq 가 Empty 상태가 되는 시점에 determinedValues 라는 배열은 원하는 모든 케이스를 가지게 됩니다.

 

아래 코드 예시는 해당 경우를 java 와 javascript 코드로 구현한 내용입니다.

 

 

< Java >

void permutation (List<Integer> sequence, int determinedCount, List<Integer> determinedValues) {
    if (sequence.isEmpty()) {
        System.out.println(determinedValues);
        return;
    }

    for (int i = 0; i < sequence.size(); i++) {
        int value = sequence.get(i);
        List<Integer> rest1 = sequence.subList(0, i);
        List<Integer> rest2 = sequence.subList(i + 1, sequence.size());
        List<Integer> newSequence = new ArrayList();
        List<Integer> newDeterminedValues = new ArrayList();
        newSequence.addAll(rest1);
        newSequence.addAll(rest2);
        newDeterminedValues.addAll(determinedValues);
        newDeterminedValues.add(value);

        permutation(newSequence, determinedCount + 1, newDeterminedValues);
    }
}
    
permutation(Arrays.asList(1,2,3,4), 0, new ArrayList());

 

< Javascript >

var sequence = [1,2,3,4]

function permutation (sequence, determinedCount, determinedValues) {
    if (sequence.length == 0) {
        console.log(determinedValues)
        return;
    }

    for (let i = 0; i < sequence.length; i++) {
        var item = sequence[i];
        var restSequence = [
            ...sequence.slice(0, i),
            ...sequence.slice(i + 1, sequence.length)
        ];
        permutation(restSequence, determinedCount + 1, [...determinedValues, item])
    }
}

permutation(sequence, 0, [])

 

< 결과 >

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