조합(Combination)

https://jun-choi-4928.medium.com/javascript로-순열과-조합-알고리즘-구현하기-21df4b536349

실제 사용

const getCombinations = function(arr, selectNumber) { 
  const results = [];
  if(selectNumber === 1) return arr.map((value) => [value]);
  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNumber - 1);
    const attached = combinations.map((combination) => [fixed, ...combination]);
    results.push(...attached);
  })
  return results;
}

const getCombinations = function(arr, selectNumber) { 
  //! selectNumber는 몇 개의 숫자를 뽑을 것이냐.
  const results = [];

  if(selectNumber === 1) return arr.map((value) => [value]); 
  // 하나만 선택한다고 했을 때
  // arr 배열의 모든 값들이 1, 2, 3, 4 이렇게 있으면 각각 [ ] 배열로 감싸서
  // [[1], [2], [3], [4]] 이렇게 바꿔주는 작업.

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    // 나머지(rest) 는 origin 배열에서 index를 제외한 나머지값을 의미한다.

    const combinations = getCombinations(rest, selectNumber - 1);
    // 맨 앞 fixed는 '무조건' 포함 되어야하므로, fixed를 제외한 나머지 숫자들을 재귀함수로 보내준다.
    // 예를들어 [1, 2, 3, 4] 에서 3개 숫자를 뽑는다고 한다면
    // [1, 2, 3], [1, 2, 4], [1, 3, 4] 등 
    // 1은 무조건 뽑고 나머지 [2, 3, 4] 에서 2개를 더 뽑아야 하는 것이므로
    // 현재 fixed인 1을 제외한 나머지와 3개 숫자 뽑는다 -> 2개 숫자 뽑는다 로 바꿔서 보내준다.

    const attached = combinations.map((combination) => [fixed, ...combination]);
    // 1을 제외한 배열의 모든 index들([2, 3, 4]) 에 대해서도 똑같이 진행한다... 만...
    // 어차피 바로 [2, 3, 4] 배열이 나온 뒤 selectNumber가 1이 될 것이므로 재귀는 끝이 난다.

    results.push(...attached);
    // 전개연산자를 통해 '깊은 복사' 를 해서 results에 넣어주고, 그것을 return 한다.
  })

  return results;
}

const example = [1,2,3,4];
const result = getCombinations(example, 3);
console.log(result);
//[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

순열(Permutations)

이번에는 나를 제외한 배열의 모든 원소에 대해서 순열을 구하는 함수에 일을 위임하면 된다. 아래의 코드를 살펴보면 정확히 다른 코드는 동일하고 배열의 나머지를 구하는 코드만 바뀌었음을 볼 수 있다.

const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열

실제 사용

unction getPermutations(arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((v) => [v]);
  else {
    arr.forEach((fixed, index, origin) => {
      const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
      const permutations = getPermutations(rest, selectNumber - 1);
      const attached = permutations.map((permutation) => [
        fixed,
        ...permutation,
      ]);
      results.push(...attached);
    });
  }

  return results;
}

const getPermutations= function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열 
    const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
    const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
    results.push(...attached); // 배열 spread syntax 로 모두다 push
  });

  return results; // 결과 담긴 results return
};

const example = [1,2,3,4];
const result = getPermutations(example, 3);
console.log(result);
// => [
//   [ 1, 2, 3 ], [ 1, 2, 4 ],
//   [ 1, 3, 2 ], [ 1, 3, 4 ],
//   [ 1, 4, 2 ], [ 1, 4, 3 ],
//   [ 2, 1, 3 ], [ 2, 1, 4 ],
//   [ 2, 3, 1 ], [ 2, 3, 4 ],
//   [ 2, 4, 1 ], [ 2, 4, 3 ],
//   [ 3, 1, 2 ], [ 3, 1, 4 ],
//   [ 3, 2, 1 ], [ 3, 2, 4 ],
//   [ 3, 4, 1 ], [ 3, 4, 2 ],
//   [ 4, 1, 2 ], [ 4, 1, 3 ],
//   [ 4, 2, 1 ], [ 4, 2, 3 ],
//   [ 4, 3, 1 ], [ 4, 3, 2 ]
// ]