순열 알고리즘

알고리즘 코딩 문제를 풀다보면 모든 경우의 수마다 한번씩 순회하여 특정한 로직을 수행해야 하는 경우가 있다.
이런 경우에 순열을 활용하면 쉽게 순회할 수 있다.

순열

순열이란 서로 다른 n개의 요소 중에서 r개를 중복없이 순서에 상관있게 선택하는 경우의 수를 의미한다.
예를들어, 전체 요소가 [a, b, c] 이라고 할 때, 2개만 선택하는 경우

• ab
• ac
• bc

이렇게 세 가지의 경우가 있다.

순열 찾는 알고리즘

만약 주어진 배열이 [a, b, c, d] 일 때 서로 다른 3개의 원소를 선택해서 나열하려면 어떻게 해야할까?
결론은, 요소를 하나씩 선택된 요소 집합으로 추가하면서, 아직 선택되지 않은 요소들의 순서를 바꿔서 하나씩 추가해서 진행하면 된다.
알고리즘의 흐름대로 진행하는 과정을 서술하자면 다음과 같다.

• a <=> a를 스왑하여 {a} 선택. {b, c, d} 남음.
• b <=> b를 스왑하여 {a, b} 선택. {c, d} 남음.
• c <=> c를 스왑하여 {a, b, c} 선택.
• c <=> d를 스왑하여 {a, b, d} 선택.
• b <=> c를 스왑하여 {a, c} 선택. {b, d} 남음.
• b <=> b를 스왑하여 {a, c, b} 선택.
• b <=> d를 스왑하여 {a, c, d} 선택.
• b <=> d를 스왑하여 {a, d} 선택. {c, b} 남음.
• c <=> c를 스왑하여 {a, d, c} 선택.
• c <=> b를 스왑하여 {a, d, b} 선택.

• a <=> b를 스왑하여 {b} 선택. {a, c, d} 남음.
• a <=> a를 스왑하여 {b, a} 선택. {c, d} 남음.
• c <=> c를 스왑하여 {b, a, c} 선택.
• c <=> d를 스왑하여 {b, a, d} 선택.
• a <=> c를 스왑하여 {b, c} 선택. {a, d} 남음.
• a <=> a를 스왑하여 {b, c, a} 선택.
• a <=> d를 스왑하여 {b, c, d} 선택.
• a <=> d를 스왑하여 {b, d} 선택. {c, a} 남음.
• c <=> c를 스왑하여 {b, d, c} 선택.
• c <=> a를 스왑하여 {b, d, a} 선택.

• a <=> c를 스왑하여 {c} 선택. {b, a, d} 남음.
• b <=> b를 스왑하여 {c, b} 선택. {a, d} 남음.
• a <=> a를 스왑하여 {c, b, a} 선택.
• a <=> d를 스왑하여 {c, b, d} 선택.
• b <=> a를 스왑하여 {c, a} 선택. {b, d} 남음.
• b <=> b를 스왑하여 {c, a, b} 선택.
• b <=> d를 스왑하여 {c, a, d} 선택.
• b <=> d를 스왑하여 {c, d} 선택. {a, b} 남음.
• a <=> a를 스왑하여 {c, d, a} 선택.
• a <=> b를 스왑하여 {c, d, b} 선택.

• a <=> d를 스왑하여 {d} 선택. {b, c, a} 남음.
• b <=> b를 스왑하여 {d, b} 선택. {c, a} 남음.
• c <=> c를 스왑하여 {d, b, c} 선택.
• c <=> a를 스왑하여 {d, b, a} 선택.
• b <=> c를 스왑하여 {d, c} 선택. {b, a} 남음.
• b <=> b를 스왑하여 {d, c, b} 선택.
• a <=> a를 스왑하여 {d, c, a} 선택.
• b <=> a를 스왑하여 {d, a} 선택. {c, b} 남음.
• c <=> c를 스왑하여 {d, a, c} 선택.
• c <=> b를 스왑하여 {d, a, b} 선택.

이렇게 총 24가지의 경우의 수가 나온다.

소스코드

function swap(array, a, b) {
    let temp = array[a];
    array[a] = array[b];
    array[b] = temp;
    return array;
}

function permutation(array, depth, n, r) {
    if (depth === r) {
        for (let i = 0; i < r; i++) {
            process.stdout.write(array[i].toString());
        }
        console.log("");
        return;
    }
    
    for (let i = depth; i < n; i++) {
        array = swap(array, depth, i); // 스왑
        permutation(array, depth + 1, n, r);
        array = swap(array, depth, i); // 되돌리기
    }
}

permutation(['a', 'b', 'c', 'd'], 0, 4, 3);

실행결과

abc
abd
acb
acd
adc
adb
bac
bad
bca
bcd
bdc
bda
cba
cbd
cab
cad
cda
cdb
dbc
dba
dcb
dca
dac
dab

이미지 출처 및 참고

Permutation via Backtracking
순열 구현하기 프로그래머스 소수 찾기 문제