[알고리즘] 조합(Combination)으로 배열의 요소 뽑기 (JavaScript)

조합으로 만들 수 있는 모든 배열을 리턴

조건

- 전달인자 : 문자열을 요소로 갖는 배열

- 출력 값 : 전달인자의 요소를 조합으로 뽑아서 배열을 만들고, 그것들을  모두 엘리먼트로 갖는 2차원 배열을 리턴

코드 작성 포인트

- 내장함수(pickOrNot)을 만들고 재귀를 사용해서, 빈 배열 result에 엘리먼트를 담기

- 배열의 인덱스를 모두 순회하면서 엘리먼트를 bucket에 담기 (담을 수도 있고 담지 않을 수도 있음)

- 함수의 전달인자는 인덱스(idx)와 조합 엘리먼트를 담을 배열(bucket)이며, 인덱스는 0부터 1씩 올리기

- 재귀 탈출조건 : 인덱스(idx)가 배열의 범위를 벗어났을 때 탈출하기

코드 작성하기

const elements = ["가", "나", "다", "라"];

let result = [];

const pickOrNot = (idx, bucket) => {
  
  if (idx === elements.length) {  // 탈출조건
    result.push(bucket)
    return;
  }

  // bucket에 해당 엘리먼트를 추가하고 다음 인덱스로 넘어감
  pickOrNot(idx + 1, bucket.concat(elements[idx]));
  
  // skip하고 다음 인덱스로 넘어감 (엘리먼트를 bucket에 추가하지 않음)
  pickOrNot(idx + 1, bucket);
  
  // idx+1 를 전달인자로 넣기 때문에 반복문이 없어도 다음 인덱스로 넘어감
};

pickOrNot(0, []);   // 0번 인덱스부터 시작하기 위해서 0을 넣어줌

result;
// [["가", "나", "다", "라"], ["가", "나", "다"], ["가", "나", "라"],
// ["가", "나"], ... ["다"], ["라"], []]

 

조합으로 만들 수 있는 모든 배열을 리턴 (정해진 개수만 뽑기)

조건

- 전달인자 : 문자열을 요소로 갖는 배열

- 출력 값 : 전달인자의 요소를 조합으로 뽑아서 배열을 만들고, 그것들을  모두 엘리먼트로 갖는 2차원 배열을 리턴

- 조합으로 2개의 엘리먼트만 뽑을 수 있음

코드 작성 포인트

1. PickOrNot 함수 사용

  - 재귀 탈출조건 : bucket 배열의 길이가 2가 되었을 때 (이미 bucket에 2개의 요소를 다 담았을 때)

  - 재귀를 멈추게 하는 조건문 : 배열의 인덱스를 모두 순회했지만, 탈출조건을 만족하지 못하는 경우를 대비

 

2. Combination 함수 사용

  - 순열(permutation) 함수와 비슷한 패턴이지만, 조합에서는 순서가 없기 때문에 중복을 제거해줘야 함

  - 재귀함수에서 배열 전달인자 호출 시, 이미 순회한 인덱스의 엘리먼트는 삭제해주기 : arr.slice(i+1)

  - (조합의 경우의 수) = (순열의 경우의 수) / (뽑는 개수)!

코드 작성하기

- pickOrNot 사용

const elements = ["가", "나", "다", "라"];

let result = [];

const pickOrNot = (idx, bucket) => {
  
  if (bucket.length===2) {  // 탈출조건
    result.push(bucket)
    return;
  }

  if (idx === elements.length) return;  // 재귀를 멈추게 하는 조건문
  
  pickOrNot(idx + 1, bucket.concat(elements[idx]));
  pickOrNot(idx + 1, bucket);
};

pickOrNot(0, []);  

result;
// [["가", "나"], ["가", "다"], ["가", "라"], ...["다", "라"]]

 

- 순열과 비슷한 Combinataion 함수 사용하기

const elements = ["가", "나", "다", "라"];

let result = [];

const combination = (arr, bucket, n) => {
  
  if (n===0) {  // 탈출조건
    result.push(bucket)
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    const sliceArr = arr.slice();
    
    // 재귀함수에는 arr의 i 인덱스까지 요소를 모두 삭제하여 조합에서 중복을 제거
    conbination(sliceArr.slice(i + 1), bucket.concat(arr[i\), n - 1);
  }
};

combination(n, []);  // n개를 뽑을 경우

result;
// [["가", "나"], ["가", "다"], ["가", "라"], ...["다", "라"]]