javascript 순열과 조합 알고리즘

조합은 배열에서 n개를 선택하는 것으로 순서가 바뀌어도 같은 것으로 취급한다.

순열은 배열에서 n개를 선택해 나열하는 것으로, 순서가 바뀌면 다른 것으로 취급한다.

자바스크립트 조합 알고리즘

const combination = (arr, select) => {
    const answer = [];
    const dfs = (idx, num, tmp, visited) => {
        if(idx === arr.length){
            return;
        }
        if(num === 0){
            answer.push(tmp);
        }
        for(let i = idx; i < arr.length; i++){
            if(!visited[i]){
                // 미방문
                visited[i] = true;
                dfs(i, num - 1, tmp.concat([arr[i]]), visited); // 선택
                visited[i] = false;
            }
        }
    }
    const visited = new Array(arr.length).fill(false);
    dfs(0, select, [], visited);
    return answer;
}

const output = combination(["사과", "배", "귤"], 2); // 2개 선택
console.log(output);

출력 값

[ 
  [ '사과', '배' ], 
  [ '사과', '귤' ], 
  [ '배', '귤' ] 
]

 

자바스크립트 순열 알고리즘

const permutation = (arr, select) => {
    const answer = [];
    const dfs = (num, tmp, visited) => {
        if(num === 0){
            answer.push(tmp);
        }
        for(let i = 0; i < arr.length; i++){
            if(!visited[i]){
                // 미방문
                visited[i] = true;
                dfs(num - 1, tmp.concat([arr[i]]), visited); // 선택
                visited[i] = false;
            }
        }
    }
    const visited = new Array(arr.length).fill(false);
    dfs(select, [], visited);
    return answer;
}

const output = permutation(["사과", "배", "귤"], 2); // 2개 선택
console.log(output);

출력 값

[
    [ '사과', '배' ],
    [ '사과', '귤' ],
    [ '배', '사과' ],
    [ '배', '귤' ],
    [ '귤', '사과' ],
    [ '귤', '배' ]
]