[알고리즘] 순열, 조합, 부분집합

1. 순열

서로 다른 n개의 배열에서 r개를 선택하는 경우의 수이며, 이때 선택하는 순서도 고려가 되어져야 한다.

표기는 nPr이다.

ex) [1, 2] 를 선택하는 것과 [2, 1]를 선택하는 것은 다른 경우이다.

 

function solution(m, arr) {
        let answer = [];

        let ch = Array.from({ length: 3 }, () => 0);
        let tmp = Array.from({ length: m }, () => 0);
        function DFS(L) {
          if (L === m) {
            answer.push(tmp.slice());
          } else {
            for (let i = 0; i < arr.length; i++) {
              if (ch[i] === 0) {
                ch[i] = 1;
                tmp[L] = arr[i];
                DFS(L + 1);
                ch[i] = 0;
              }
            }
          }
        }
        DFS(0);
        return answer;
}

 

 

2.조합

서로 다른 n개의 배열에서 r개를 선택하는 경우의 수를 조합이라고 하며, nCr로 표기한다.

이때, r개를 선택할 경우 아이템의 순서는 무시한다.

ex ) [1,2]를 선택하든, [2,1]를 선택하든 같다고 취급한다.

 

function solution(n, m) {
        let answer = [];
        let ch = Array({ length: n }, () => 0);
        let tmp = Array({ length: m }, () => 0);
        function DFS(L, S) {
          if (L == m) {
            answer.push(tmp.slice());
          } else {
            for (let i = S; i <= n; i++) {
              tmp[L] = i;
              DFS(L + 1, i + 1);
            }
          }
        }
        DFS(0, 1);
        return answer;
}

 

 

3. 부분집합

집합의 원소가 N개일 때, 공집합을 포함한 부분집합의 수는 2^N개

function solution(n) {
        let answer = [];
        let ch = Array.from({ length: n + 1 }, () => 0);
        function DFS(v) {
          if (v === n + 1) {
            let tmp = "";
            for (let i = 1; i <= n; i++) {
              if (ch[i] === 1) tmp += i + " ";
            }
            answer.push(tmp.trim());
          } else {
            ch[v] = 1;
            DFS(v + 1);
            ch[v] = 0;
            DFS(v + 1);
          }
        }
        DFS(1);
        return answer;
}