[알고리즘] 순열과 조합 구현(JS)

오늘은 순열과 조합, 부분집합 구현에 대해 간단히 정리해보려고 한다.
순서는 순열, 조합, 부분집합 순으로 진행하려고 한다.

💡 순열

순열이란, 서로 다른 N개의 원소들 중에 R개의 원소들을 뽑을 때, 순서를 고려하여 선택하는 것을 말한다. 순열은 아래와 같은 수식으로 경우의 수를 구할 수 있다. 아래와 같이 총 4개의 수 중 2개를 선택할 경우(4P2)를 순열 코드로 구현하면 다음과 같다.

/*
 * N : 총 N 개의 수
 * R : 뽑을 수의 개수
 * isSelected : 선택 여부 저장
 * answer : 뽑은 수를 저장
 * permutation : 순열 함수
 */

let N = 4;
let R = 2;
let isSelected = Array(N + 1).fill(false);
let answer = [];

// 순열
const permutation = (cnt) => {
  // cnt가 R개일 때
  if (cnt == R) {
    console.log(answer);
    return;
  }

  for (let i = 1; i <= N; i++) {
    // 이미 선택됐다면, 다음으로
    if (isSelected[i]) continue;

    // 선택이 안된 수라면 다시 선택
    isSelected[i] = true;

    // 선택된 수 저장
    answer[cnt] = i;

    // 다음 수 뽑으러 가기
    permutation(cnt + 1);

    // 선택된 수 다시 돌리기
    isSelected[i] = false;
  }
};

// 수열 함수 실행
permutation(0);

// 출력
// [ 1, 2 ]
// [ 1, 3 ]
// [ 1, 4 ]
// [ 2, 1 ]
// [ 2, 3 ]
// [ 2, 4 ]
// [ 3, 1 ]
// [ 3, 2 ]
// [ 3, 4 ]
// [ 4, 1 ]
// [ 4, 2 ]
// [ 4, 3 ]

💡 조합

조합은 순열과 달리 순서를 고려하지 않고 선택한다. 즉, 서로 다른 N개의 원소 중 R개를 순서에 상관없이 선택하는 것을 말한다.
아래와 같이 4개의 수 중 2개를 선택하여 조합할 때 다음과 같이 코드를 작성할 수 있다.

/*
 * N : 총 N 개의 수
 * R : 뽑을 수의 개수
 * answer : 뽑은 수를 저장
 * combination : 조합 함수
 */

let N = 4;
let R = 2;
let answer = [];

// 조합
const combination = (start, cnt) => {
  // 총 R개의 수를 뽑았을 때,
  if (cnt == R) {
    console.log(answer);
    return;
  }

  // 시작 위치부터 N까지 추출
  for (let i = start; i <= N; i++) {
    // 뽑은 수 저장
    answer[cnt] = i;

    // 다음 수 뽑으로 가기
    combination(i + 1, cnt + 1);
  }
};

// 조합
combination(1, 0);

// 출력
// [ 1, 2 ]
// [ 1, 3 ]
// [ 1, 4 ]
// [ 2, 3 ]
// [ 2, 4 ]
// [ 3, 4 ]

💡 멱집합

마지막으로 멱집합은 특정 집합에서 구할 수 있는 모든 부분집합을 의미한다.
예를 들어, [1,2,3,4] 원소를 가지는 집합 S가 존재할 때, 집합 S에 대한 부분집합은 아래 코드와 같이 구할 수 있다.

/*
 * N : 총 N 개의 수
 * S : 집합
 * isSelected : 선택 여부 저장
 * subset : 부분 집합 생성 함수
 * print : 출력 함수
 */

let N = 4;
let S = [1, 2, 3, 4];
let isSelected = Array(N).fill(false);

// 출력 함수
const print = (selected) => {
  let answer = selected.map((state, index) => (state ? S[index] : "X"));
  console.log(answer.join(" "));
};

// 부분집합 생성
const subset = (idx) => {
  // 기저조건
  if (idx == N) {
    print(isSelected);
    return;
  }

  // 선택한 경우
  isSelected[idx] = true;
  subset(idx + 1);

  // 선택하지 않은 경우
  isSelected[idx] = false;
  subset(idx + 1);
};

subset(0);

// 출력
// 1 2 3 4
// 1 2 3 X
// 1 2 X 4
// 1 2 X X
// 1 X 3 4
// 1 X 3 X
// 1 X X 4
// 1 X X X
// X 2 3 4
// X 2 3 X
// X 2 X 4
// X 2 X X
// X X 3 4
// X X 3 X
// X X X 4
// X X X X