개요

JS엔 파이썬과 달리 itertools이 없다. 그래서 직접 구현해야하는데, 수많은 방법중에 이 방법을 택했다.

방향

1. 시간이 적은 코테에서 바로 사용할 수 있도록 간단해야할것
2. 하나의 Base코드에서 순열, 조합, 중복순열, 중복조합 모든 것을 쉽게 구현할 수 있어야할 것

구현

기본적으로 visited를 사용한다.
1. 재귀를 할 때 inorder형식을 사용
2. for문의 초기값이 0(순열일 때) 혹은 이전재귀idx(조합일 때)
3. 중복을 구현할 땐, visited형식을 뺀다

순열(Base)

function permutations(arr, r){
    if(r === 0)
        return [];
    const result = [];
    const visited = new Array(arr.length).fill(false);
    function recur(sub_arr){
        if(sub_arr.length === r){
            result.push(sub_arr);
            return;
        }
        for (let i = 0; i < arr.length; i++) {
            if(visited[i])
                continue;
            visited[i] = true;
            recur([...sub_arr, arr[i]]);
            visited[i] = false;
        }
    }
    recur([]);
    return result;
}

중복순열

단순한 N의 r제곱

function permutations_w(arr, r){
    if(r === 0)
        return [];
    const result = [];
    //const visited = new Array(arr.length).fill(false);
    function recur(sub_arr){
        if(sub_arr.length === r){
            result.push(sub_arr);
            return;
        }
        for (let i = 0; i < arr.length; i++) {
            //if(visited[i])
            //    continue;
            visited[i] = true;
            recur([...sub_arr, arr[i]]);
            visited[i] = false;
        }
    }
    recur([]);
    return result;
}

조합

function combinations(arr, r){
    if(r === 0)
        return [];
    const result = [];
    const visited = new Array(arr.length).fill(false);
    function recur(sub_arr, idx){ // idx 매개변수 추가
        if(sub_arr.length === r){
            result.push(sub_arr);
            return;
        }
        for (let i = idx; i < arr.length; i++) { // i초기값 0->idx
            if(visited[i])
                continue;
            visited[i] = true;
            recur([...sub_arr, arr[i]], i); // i 매개변수 추가
            visited[i] = false;
        }
    }
    recur([], 0);
    return result;
}

중복조합

조합코드에서 if(visited[i])만 제거

function combinations_w(arr, r){
    if(r === 0)
        return [];
    const result = [];
    //const visited = new Array(arr.length).fill(false);
    function recur(sub_arr, idx){
        if(sub_arr.length === r){
            result.push(sub_arr);
            return;
        }
        for (let i = idx; i < arr.length; i++) {
            //if(visited[i])
                //continue;
            //visited[i] = true;
            recur([...sub_arr, arr[i]], i);
            //visited[i] = false;
        }
    }
    recur([], 0);
    return result;
}

참고: 하나의 함수로 구현

조합, 중복조합, 순열, 중복순열을 하나의 함수로 구현하면 다음과 같다.

function generateSequences(arr, r, is_repetition, is_combination) {
    if (r === 0) return [];

    const result = [];
    const visited = new Array(arr.length).fill(false);

    function recur(sub_arr, idx) {
        if (sub_arr.length === r) {
            result.push(sub_arr);
            return;
        }

        for (let i = is_combination ? idx : 0; i < arr.length; i++) {
            if (is_repetition || !visited[i]) {
                visited[i] = true;
                recur([...sub_arr, arr[i]], i);
                visited[i] = false;
            }
        }
    }

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

// 사용 예시
const arr = [1, 2, 3, 4, 5];

// 순열
let permutations = generateSequences(arr, 2, false, false);
console.log(`Permutations Length: ${permutations.length}`);
console.log(permutations);
console.log(`-`.repeat(10));

// 조합
let combinations = generateSequences(arr, 2, false, true);
console.log(`Combinations Length: ${combinations.length}`);
console.log(combinations);
console.log(`-`.repeat(10));
// 중복 순열
let permutationsWithRepetition = generateSequences(arr, 2, true, false);
console.log(`Permutations with Repetition Length: ${permutationsWithRepetition.length}`);
console.log(permutationsWithRepetition);
console.log(`-`.repeat(10));
// 중복 조합
let combinationsWithRepetition = generateSequences(arr, 2, true, true);
console.log(`Combinations with Repetition Length: ${combinationsWithRepetition.length}`);
console.log(combinationsWithRepetition);
console.log(`-`.repeat(10));

$ node "p:\CodingTest\temp.js"
Permutations Length: 20
[
  [ 1, 2 ], [ 1, 3 ], [ 1, 4 ],
  [ 1, 5 ], [ 2, 1 ], [ 2, 3 ],
  [ 2, 4 ], [ 2, 5 ], [ 3, 1 ],
  [ 3, 2 ], [ 3, 4 ], [ 3, 5 ],
  [ 4, 1 ], [ 4, 2 ], [ 4, 3 ],
  [ 4, 5 ], [ 5, 1 ], [ 5, 2 ],
  [ 5, 3 ], [ 5, 4 ]
]
----------
Combinations Length: 10
[
  [ 1, 2 ], [ 1, 3 ],
  [ 1, 4 ], [ 1, 5 ],
  [ 2, 3 ], [ 2, 4 ],
  [ 2, 5 ], [ 3, 4 ],
  [ 3, 5 ], [ 4, 5 ]
]
----------
Permutations with Repetition Length: 25
[
  [ 1, 1 ], [ 1, 2 ], [ 1, 3 ],
  [ 1, 4 ], [ 1, 5 ], [ 2, 1 ],
  [ 2, 2 ], [ 2, 3 ], [ 2, 4 ],
  [ 2, 5 ], [ 3, 1 ], [ 3, 2 ],
  [ 3, 3 ], [ 3, 4 ], [ 3, 5 ],
  [ 4, 1 ], [ 4, 2 ], [ 4, 3 ],
  [ 4, 4 ], [ 4, 5 ], [ 5, 1 ],
  [ 5, 2 ], [ 5, 3 ], [ 5, 4 ],
  [ 5, 5 ]
]
----------
Combinations with Repetition Length: 15
[
  [ 1, 1 ], [ 1, 2 ],
  [ 1, 3 ], [ 1, 4 ],
  [ 1, 5 ], [ 2, 2 ],
  [ 2, 3 ], [ 2, 4 ],
  [ 2, 5 ], [ 3, 3 ],
  [ 3, 4 ], [ 3, 5 ],
  [ 4, 4 ], [ 4, 5 ],
  [ 5, 5 ]
]
----------