Recursion - 순열

순열

순열은 멱집합의 반대?되는 개념이라고 생각하면쉽다

우리가 멱집합을 구할 때는 순서가 달라도 원소가 같으면 동일한 것으로 취급했지만

순열을 구할때는 순서가 다르면 다른 개체?로 취급한다

예를 들어 집합 {a,b,c}의 순열을 구하라 고 한다면

{a,b,c}
{a,c,b}
{b,a,c}
{b,c,a}
{c,a,b}
{c,b,a}

총 6개의 집합을 구할 수 있다

문제

집합이 주어졌을 때 그 집합의 모든 순열을 구하는 재귀함수를 만들어라

접근 방식

위에 {a,b,c}의 순열을 나열하면서 느낀 것이 있는가?

a + {b,c}의 순열을
b + {a,c}의 순열을
c + {a,b}의 순열을

구한 것과 같다 즉 앞의 원소를 제외한 나머지 원소의 순열을 구한 뒤에 합쳐주면 모든 순열을 구할 수 있다

코드

function swap(arr, i, number){
    let temp = arr[i];
    arr[i] = arr[number];
    arr[number] = temp;
}

function permutation(number) {
    if(number=== set.length){
        console.log(set);
        return ;
    }

    for(let i=number; i<set.length;i++){
        swap(set,i,number);
        permutation(number+1);
        swap(set,i,number);
    }
}

permutation(0);

set은 집합이고 초기값은 0으로 설정해준다

배열을 생성하거나 넘겨주기 보다는 같은 배열 안에서 index(number)를 이용해 가만히 둘 원소, 순열을 구할 원소들로 구분지었다

{a,b,c,d}집합을 예를 들면

처음에는 a를 놔두고 {b,c,d}의 순열을 구하기 위해 다시 재귀 호출 --- 1

a,b를 놔두고 {c,d}의 순열을 구하기 위해 다시 재귀 호출 --- 2

a,b,c를 놔두고 {d}의 순열을 구하기 위해 다시 재귀 호출을 하면 --- 3

number=== set.length이기 때문에 set을 그냥 출력한다 (a,b,c,d)

3번 재귀 호출을 빠져 나온 뒤에 2번으로 돌아가서 {c,d}의 순열을 마저 구해야하는데 이젠 d가 앞으로 가야하니

swap함수를 이용해 {d,c}를 구해 (a,b,d,c}를 출력하고 배열의 순서를 원위치 시키기위해 다시 swap호출...