[구현] JS 순열/ 조합

순열

function getPermutations(arr, r) {
    const result = [];

    function permute(temp, remaining) {
        if (temp.length === r) {
            result.push([...temp]); // r개의 길이만큼 선택한 경우 결과에 추가
            return;
        }

        for (let i = 0; i < remaining.length; i++) {
            permute([...temp, remaining[i]], [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
        }
    }

    permute([], arr);
    return result;
}

// 사용 예시
const arr = [1, 2, 3];
console.log(getPermutations(arr, 2));
// 출력: [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]

- 사용한 원소를 하나씩 제거해서 다음으로 넘기는 방식

조합

function getCombinations(arr, r) {
    const result = [];

    function combine(temp, start) {
        if (temp.length === r) {
            result.push([...temp]); // r개의 길이만큼 선택한 경우 결과에 추가
            return;
        }

        for (let i = start; i < arr.length; i++) {
            combine([...temp, arr[i]], i + 1); // i + 1로 다음 위치부터 선택
        }
    }

    combine([], 0);
    return result;
}

// 사용 예시
const arr2 = [1, 2, 3];
console.log(getCombinations(arr2, 2));
// 출력: [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]

- 앞에서부터 모든 조합을 만들고, 계속 앞으로 나아가는 방식