Javascript 순열, 조합 알고리즘 구현하기

순열 

 

순서가 존재하고, N개 중 K개를 선택하는 경우 순열이라고 합니다.

 

visited로 0부터 N까지 방문했는지 확인하고 매번 0부터 N까지 반복문을 동작하여 반환합니다.

 

Permutation

 

const visited = Array.from({ length: N }, () => false);

const combi = (num, arr) => {
  if (num === 0) {
    console.log(arr);
    return;
  }

  for (let i = 0; i < N; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    combi(num - 1, [...arr, i]);
    visited[i] = false;
  }
};

  /**
   * N은 전체 개수, K는 뽑고자 하는 개수
   */
  combi(3, []);

 

 

출력 결과

 

    [ 0, 1, 2 ]    [ 0, 1, 3 ]    [ 0, 2, 1 ]    [ 0, 2, 3 ]    [ 0, 3, 1 ]    [ 0, 3, 2 ]
    [ 1, 0, 2 ]    [ 1, 0, 3 ]    [ 1, 2, 0 ]    [ 1, 2, 3 ]    [ 1, 3, 0 ]    [ 1, 3, 2 ]
    [ 2, 0, 1 ]    [ 2, 0, 3 ]    [ 2, 1, 0 ]    [ 2, 1, 3 ]    [ 2, 3, 0 ]    [ 2, 3, 1 ]
    [ 3, 0, 1 ]    [ 3, 0, 2 ]    [ 3, 1, 0 ]    [ 3, 1, 2 ]    [ 3, 2, 0 ]    [ 3, 2, 1 ]

 

 

 

조합

 

순서를 생각하지 않고, N개 중 K개를 선택하는 경우를 조합이라고 합니다.

 

구현 방법은 선택한 인덱스를 전달하여 중복되지 않도록 선택한 인덱스 + 1부터 반복문을 실행해 조합 결과를 반환합니다.

 

Combination

 

const combi = (selectIndex, arr) => {
  if (arr.length === K) {
    console.log(arr);
    return;
  }
  // console.log(num, arr);

  for (let i = selectIndex + 1; i < N; i++) {
    combi(i, [...arr, i]);
  }
};


  /**
   * N은 전체 개수, K는 뽑고자 하는 개수
   */
  combi(-1, []);

 

 

출력 결과

 

    [ 0, 1, 2 ]
    [ 0, 1, 3 ]
    [ 0, 2, 3 ]
    [ 1, 2, 3 ]