순열, 조합 알고리즘 이해하기

순열, 조합 알고리즘은 코딩테스트에서 빈번하게 출제 된다. 그럼에도 항상 마주치면 구글링을한다..

따라서 오늘 순열, 조합 완벽하게 이해하고 끝내보려고 한다.

---

조합 재귀 구현

조합의 수도코드는 다음과 같다.

 

배열 [1, 2, 3, 4] 에서 3개를 선택하는 조합을 구할때

 

1을 고정 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다. -> [1(고정) + 각각 뽑은거]

2를 고정 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다. -> [2(고정) + 각각 뽑은거]

3을 고정 -> 나머지 [4] 중에서 2개씩 조합을 구한다.

4를 고정 -> 나머지 [] 에서 2개씩 조합을 구한다.

 

여기서 나머지 배열에 대해 조합을 구할 때는, 재귀함수를 사용하면 된다.

 

- 기저조건 : 1개를 뽑을때, 모든 배열의 원소를 하나씩 선택해 배열로 리턴한다.

- forEach문을 이용해, 배열의 모든 원소를 처음부터 끝까지 한번씩 고정되게 한다.

- 고정된 값을 제와한 나머지 뒤 배열에 대해 조합을 구한다. 이때, 선택하는 개수를 하나씩 줄여간다.

- 이렇게 조합을 만들어온 결과에 고정된 값을 붙이고, 전개 구문(...)을 이용해 리턴할 배열에 넣는다.

- 배열보다 뽑는 개수가 더 많을 경우 빈 배열이 리턴되기 때문에, 최종 결과값에 포함되지 않는다.

 

let arr = [1, 2, 3, 4]

function getCombinations(arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((item) => item);

  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;
}

console.log(getCombinations(arr, 3)); //[ [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

 

1, 2, 3 중에 2개를 뽑는 조합과정을 작성하면 다음과 같다. (수도코드라 읽기 힘들수도있다..)

---

순열 재귀 구현

순열은 순서를 고려한 뽑기이다.

 

순열 nPr = 조합 nCr * r!

 

조합에 순서를 부여하면 순열이 된다.

 

조합 코드에서 나머지 배열을 구하는 코드만 바꾸면, 해결할 수 있다.

const rest = origin.slice(index + 1); //조합을 구할때 나머지 변수
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; //순열을 구할때 나머지 변수

조합의 rest는 해당 고정값을 제외한 나머지 뒤에 부분이지만,

순열의 rest는 해당 고정값을 제외한 나머지 배열을 rest로 남기는 코드다.

 

전체 코드는 다음과 같다.

let arr = [1, 2, 3]

function getPermutations(arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((item) => [item]);

  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;
}

console.log(getPermutations(arr, 2)); //[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]

다음은 내가 이해하려고 쓴 [1, 2, 3] 중에서 2개를 선택할때의 순열 수도코드이다.

---

순열 반복문 구현

for반복문을 r번 중첩하면 된다. 이 때, 반복문에 의해 선택된 i, j, k는 모든 다른 값을 가르키도록 강제 해야한다.

 

const arr = [1, 2, 3, 4];
const ans = [];

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    for (let k = 0; k < arr.length; k++) {
      if (arr[i] === arr[j] || arr[i] === arr[k] || arr[j] === arr[k]) {
        continue;
      }
      const current = [arr[i], arr[j], arr[k]];
      ans.push(current);
    }
  }
}

console.log(ans);

 

n개중 r개를 뽑아 나열하는 순열알고리즘을 짜려면, r개의 중첩 for문이 필요하다.

 

참고자료
 - https://pul8219.github.io/algorithm/algorithm-permutation-and-combination/
 - https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-21df4b536349