Javascript 순열과 조합;재귀

주말동안 ChatGPT 선생님에게 질문하며 공부한 내용을 정리하였다.

1. 코드로 보는 순열과 조합의 차이

function permutation(arr) {
    var result = [];
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length; j++) {
            if (i !== j) {
                result.push([arr[i], arr[j]]);
            }
        }
    }
    return result;
}
console.log(permutation(['a', 'b', 'c']));
// Output: [['a', 'b'], ['a', 'c'], ['b', 'a'], ['b', 'c'], ['c', 'a'], ['c', 'b']]

function combination(arr) {
    var result = [];
    for (var i = 0; i < arr.length; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            result.push([arr[i], arr[j]]);
        }
    }
    return result;
}
console.log(combination(['a', 'b', 'c']));
// Output: [['a', 'b'], ['a', 'c'], ['b', 'c']]

보시다시피 순열 함수는 입력 배열에 있는 요소 쌍의 가능한 모든 순서를 반환하는 반면 조합 함수는 순서에 관계없이 입력 배열에 있는 요소 쌍의 가능한 모든 하위 집합을 반환합니다.

2. 직접 작성해보자

2-1. 코드

1번의 예시코드는 간단하게 페어(1쌍), 즉 길이가 2인 순서들만 반환하는 고정 코드이기 때문에 nPk든 nCk든 k가 3이상에서도 돌아갈 수 있는 순열/조합 함수가 필요하다. 지정한 길이의 순서가 나올때까지 재귀적으로 돌다가 순열 혹은 조합 리스트를 리턴하는 자바스크립트 코드를 작성해보았다.

function p(arr,len){
    let r = [];
    const h = (ori,temp, start) => {
        if (temp.length === len)
            return r.push(temp);
            
        for(let i = start; i < ori.length; i++){
            let curr = ori.slice();
            let next = curr.splice(i,1);
            h(curr, temp.concat(next), 0);
        }            
        return 0;
    };
    
    h(arr, [], 0);
    
    return r;
    
}
console.log(p([1,2,3],2))
/*[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], 
[ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]*/


function c(arr, len) {
    let r = [];
    
    const h = (ori, temp, start) => {
        if (temp.length === len)
            return r.push(temp);

        for (let i = start; i < ori.length; i++) {
            let curr = ori.slice();
            let next = curr.splice(i,1);
            h(curr, temp.concat(next), i);
        }
    };

    h(arr, [], 0);
    return r;
}
console.log(c([1, 2, 3], 2));
/*[ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]*/

h의 start인자의 값이 차이가 있다. 어째서 이 차이가 순열 혹은 조합에 대한 결과를 리턴해주는지 ChatGPT님께 여쭈어보았다.

2-2. ChatGPT의 부연설명

순열 및 조합 함수는 모두 "h"라는 재귀 함수를 사용하여 입력 배열에서 요소의 가능한 모든 배열을 생성합니다. 두 함수의 주요 차이점은 "h" 함수에 전달되는 세 번째 인수 "start"의 값입니다.

순열 함수는 각 재귀 호출에 대해 인덱스 0에서 "h" 함수를 시작합니다. 이는 함수가 순열의 각 위치에 대해 배열의 가능한 모든 요소를 ​​고려하여 반복되는 요소가 있는 순열을 포함하여 배열의 요소에 대한 모든 가능한 순열을 생성함을 의미합니다.

반면 조합 함수는 각 재귀 호출에 대해 현재 인덱스에서 "h" 함수를 시작합니다. 즉, 함수는 조합의 각 위치에 대해 현재 인덱스 뒤에 오는 요소만 고려하여 반복되는 요소 없이 배열 요소의 가능한 모든 조합을 생성합니다.

그것은 항아리에서 사탕을 따는 것과 같습니다. 순열에서는 이전에 이미 골랐던 사탕을 다시 집어 넣을 수 있지만 조합에서는 같은 사탕을 다시 집을 수 없습니다.

2-3. 재귀 이벤트 시각화

3. 패션개발자의 생각

어쩌면 이런 저런 핑계로 차일피일 미루어왔던 알고리즘 공부와 javascript 파고들기가 ChatGPT 선생님의 등장으로 이젠 가능할지도 모르겠다. 너무 신기하고 또 무섭기도 하지만 지구가 로봇에 지배당하기 전까진 그들의 가르침을 받고자한다.