순열, 조합, 중복순열 구하기

한번에 이해하는게 매우 힘들었다. 참고 블로그를 보고 해결의 실마리를 찾고 구현에 성공하였다.
사실, 전에 공부했었지만 다시 해보려니 까먹어서 블로그에 작성해놓으면 한결 낫지 않을까 하는 마음에 작성해 놓으려고 한다.

기본 규칙

순열, 조합, 중복순열 모두 같은 로직으로 진행된다.

배열에서 3개를 선택하는 경우
1. 하나의 수를 선택한다.
2. 3개를 뽑는 순열중 하나의 수를 선택했으니 남은 배열에서 2개를 선택해야한다.

이 두 과정을 반복하면 순열,조합,중복순열을 구할 수 있다.
순열, 조합, 중복순열들은 서로 남은 배열을 설정해주는 과정에서만 차이가 있다.

코드를 먼저 보고 설명하겠다. 순열을 예로 들겠다.

순열 코드

function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr.filter((_, index) => index !== idx);
    const permuationArr = permutation(restArr, selectNum - 1);
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
}

순열을 구하는 permutation함수가 있다.

1. 입력받은 arr을 forEach로 순회하며 처음에 뽑을 fixer를 선택한다.
2. fixer를 제외한 남은 애들을 갖고 새로운 restArr을 만든다.
3. permutationArr에는 restArr로 selectNum-1의 순열이 들어있다.
4. combineFixer에 fixer와 permutationArr과 합친 순열을 만든다.
5. result에 넣는다.
   끝의 수까지 반복한다.

재귀형식으로 이루어진다. selectNum이 하나만 남았다면 배열의 수 하나하나를 각각의 순열로 만들 수 있기 때문에 하나의 작은 배열로 다 바꿔준다.

말로만해서는 이해가 힘들다. 아래에 예시를 들어서 다시 설명하겠다.

[1,2,3,4] 에서 2개를 뽑은 경우의 수를 구하여라.

• permutation([1,2,3,4],2)

1. fixer: 1, restArr: [2,3,4], permutationArr: permutation([2,3,4],1)

1-1. permutation([2,3,4],1)
selectNum ===1 => return [[2],[3],[4]]

이것은 위의 permuatitonArr이 된다.

즉
fixer: 1,
restArr: [2,3,4],
permutationArr: [[2],[3],[4]],
combineFixer: [[1,2],[1,3],[1,4]]

result.push([[1,2],[1,3],[1,4]])

이렇게 1을 먼저 골랐을 때 순열을 구하는 순서이다. 이렇게 2,3,4를 반복한다.

이 규칙만 이해한다면 조합과 중복 순열은 손쉽게 생각할 수 있을 것이다.

조합은 선택했던 모든 것들은 다시는 선택하면 안되기 때문에 restArr이 fixer의 뒤에 값이면 된다.
중복 순열은 현재 fixer까지 다시 선택할 수 있기 때문에 restArr이 기본 arr이면된다. (기본 arr은 forEach구문의 3번째 인자를 활용하면 된다.)

아래에 조합과 중복순열일 때 각각의 코드를 써놓고 포스팅을 끝내야겠다~~!

조합 코드

function combination(arr, selectNum) {
  const result = [];
  if (selectNum === 1) return arr.map((v) => [v]);
  arr.forEach((v, idx, arr) => {
    const fixed = v;
    const restArr = arr.slice(idx + 1);
    const combinationArr = combination(restArr, selectNum - 1);
    const combineFix = combinationArr.map((v) => [fixed, ...v]);
    result.push(...combineFix);
  });
  return result;
}

중복순열 코드

function permutation(arr, selectNum) {
  const result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixed = v;
    const restArr = arr;
    const permutationArr = permutation(restArr, selectNum - 1);
    const combineFix = permutationArr.map((v) => [fixed, ...v]);
    result.push(...combineFix);
  });
  return result;
}

알고리즘에서 간단하게 조합을 응용할 경우

알고리즘에서 조합,순열을 이용할 경우가 많다. 하지만 매번 저렇게 길게 써주기 귀찮을 때 for문을 이용해 보다 간단하게 작성할 수 있다.

아래와 같은 경우는 dfs의 outer함수의 지역변수 answer가 있을 때 간단하게 작성할 수 있다.

기본적인 로직은 위에서 작성한 로직과 같다.

arr에 배열이 아닌 sum을 두고 3개까지 선택했을 때의 합을 구할 수 도 있고 다양하게 활용할 수 있다.

이 코드에서 if종료조건의 else를 빼고 아래와 같이 작성했을 때 시간이 훨씬 오래걸리는 현상이 있었다. else로 한번 거쳐주는것도 중요하다고 생각된다.

if (num === 3) answer.push([...arr]);
for (let i = 0; i < nums.length; i++) {
  arr.push(nums[i]);
  dfs(nums.slice(i + 1), num + 1, arr);
  arr.pop();
}

let answer = [];

const dfs = (nums, num, arr = []) => {
  //3개를 선택한다는가정에 3개가 선택 됐다면 출력
  if (num === 3) answer.push([...arr]);
  else {
    for (let i = 0; i < nums.length; i++) {
      arr.push(nums[i]);
      dfs(nums.slice(i + 1), num + 1, arr);
      arr.pop();
    }
  }
};
dfs([1, 2, 3, 4], 0);
console.log(answer); //[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

참조 : 참조 링크