[알고리즘] 순열과 조합

순열과 조합은 경우의 수를 구할 때 많이 활용되는 수학적 개념이다. 이 개념은 개발 분야에서도 리스트, 배열 등의 데이터를 조합하거나 순서를 지정할 때 자주 사용된다.

순열(Permutation)이란?

• n개의 원소에서 r개를 순서 있게 뽑는 경우의 수다.
  예시: 3명 중 2명을 뽑아 줄을 세우는 모든 방법의 수
  P(3,2) = 6
  

JavaScript에서는 재귀 함수를 활용해 구현할 수 있고,
Python에서는 itertools 모듈로 간단하게 구현된다.

function getPermutations(arr, selectNumber) {
  if (selectNumber === 1) return arr.map((v) => [v]);
  const result = [];
  arr.forEach((v, idx, origin) => {
    const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)];
    const permutations = getPermutations(rest, selectNumber - 1);
    permutations.forEach((permutation) => {
      result.push([v, ...permutation]);
    });
  });
  return result;
}

import itertools

arr = [1, 2, 3]
result = list(itertools.permutations(arr, 2))
print(result)

조합(Combination)이란?

n개의 원소에서 r개를 순서와 상관없이 뽑는 경우의 수다.
예시: 3명 중 2명을 뽑는 방법의 수
C(3,2) = 3

function getCombinations(arr, selectNumber) {
  if (selectNumber === 1) return arr.map((v) => [v]);
  const result = [];
  arr.forEach((v, idx, origin) => {
    const rest = origin.slice(idx + 1);
    const combinations = getCombinations(rest, selectNumber - 1);
    combinations.forEach((combination) => {
      result.push([v, ...combination]);
    });
  });
  return result;
}

import itertools

result = list(itertools.combinations(arr, 2))
print(result)