📌 javascript 개념 #11 조합 / 수학기본이론 (3)

수학기본이론 / 경우의 수 / 조합

조합 (combination) : nCr

: 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열
=> for문과 재귀함수로 표현가능하며, 완전탐색에 해당한다.

예시사진

4개의 숫자카드에서 2개를 뽑는 경우

조합 예제 코드 (1) for loop

// >> for문으로 구현
let input = [1, 2, 3, 4];
let count = 0;

function combination(arr) {
  // for 문 개수 => 뽑는 개수 == r ==> 2
  // 인덱스 3, 즉 vaule 4가 오게 되면
  // j는 4가 된다.
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      count++;
      console.log(arr[i], arr[j]);
    }
  }
}

combination(input);
console.log(count);

/* 
1 2
1 3
1 4
2 3
2 4
3 4
6
*/

count 변수는 총 몇번의 경우의 수가 있는지 카운팅하기 위한 변수 이며, 뽑는 갯수만큼 for문의 갯수가 된다.
처음에는 다 뽑을 수 있기 때문에 i++을 해주고, j는 i 이후의 값만 선택할 수 있도록 해주었다.
만약 i = 3 (value = 4)일 경우, j는 index = 4가 되어 자동적으로 for문이 skip처리 된다. -> 따라서, 예외처리를 따로 해주지 않음

조합 예제 코드 (2) 재귀함수

// >> 재귀함수로 구현
let Input = [1, 2, 3, 4]; // 4C2
let Output = [];
let Count = 0;

// arr, data : Output에 저장될 값, 
// s : 사작하는 값, 
// idx : 현재 위치(for loop starting point), 
// r : 끝나는 값

function combination(arr, data, s, idx, r) {
  if (s == r) {
    Count++;
    console.log(data);
    return;
  } 
  // break 포인트 

  for (let i = idx; arr.length - i >= r - s; i++) {
    data[s] = arr[i];
    combination(arr, data, s + 1, i + 1, r);
  }
}

combination(Input, Output, 0, 0, 2);
console.log(Count);

/*
[ 1, 2 ]
[ 1, 3 ]
[ 1, 4 ]
[ 2, 3 ]
[ 2, 4 ]
[ 3, 4 ]
6
*/

재귀함수에서는 output이라는 별도 array를 줘서 뽑은 것을 배열에 저장한다.
s가 r과 동일하다면, 멈추게 해주는 break 포인트를 만들어준다.
for문 : i는 index만큼 돌면서 length에서 -1을 한것이 r - s 보다 크거나 같을때만 실행시켜준다. data 부분에는 arr 값을 복사해주고 combination에서 각각의 요소들을 매개변수로 넣어주며, s와 index는 하나 증가시켜준다.