✅ 순열과 조합

자몽·2021년 7월 30일

알고리즘

목록 보기

3/31

알고리즘 문제들을 풀면서 경우의 수를 구하는 방법을 그때그때마다 무식하게 for을 중첩해서 돌려가며 해결했었다.
조금 더 효율적으로 문제를 풀기 위해서 순열과 조합을 공부하게 되었다.

시작하기에 앞서 이번 포스팅은 "https://velog.io/@proshy/JS순열조합중복순열-구하기" 를 대부분 참고하여 만들어졌다는 것을 공지하고자 한다.

✅ 순열과 조합

const arr = [1,2,3];
위와 같은 배열을 순열/조합/중복 순열을 통해 경우의 수를 구한다고 생각해보자.

📕 순열

nPr
permutation: 서로 다른 n개 중에 r개를 선택하는 경우의 수[순서 상관 O]

3P2 = 6
경우의 수: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2] => 6개

코드는 다음과 같다.

// numbers에서는 배열을 입력받고, range는 nPr에서 'r'을 담당한다.
const permutation=(numbers, range)=>{
  
  let output = [];
  // r이 1인 경우에는 배열 내부 값들이 그대로 output이 된다.
  if(range===1) return numbers.map(num => [num]);
  // forEach((요소, 인덱스, 배열)=> ...
  
  numbers.forEach((number, index, temp)=>{
    // 중심이 될 수가 들어있음
    const mainNumber = number;
    // 중심을 제외한 수들은 나머지가 된다.
    const subNumbers = numbers.filter((_,idx) => index!==idx);
    
    // 재귀를 사용해 반복되는 작업을 처리한다.
    const rePermutation = permutation(subNumbers, range-1);
    // subNumbers를 통해 만들어낸 결과를 mainNumber에 덧붙인다.
    const combine = rePermutation.map(num=>[mainNumber, ...num]);
    // 이중배열 풀어주기
    output.push(...combine);
  });
return output;
}

한 가지 주의해서 보야야 할 부분은 다음과 같다.
const subNumbers = numbers.filter((_,idx) => index!==idx);
순열은 선택했던 것들도 순서에 따라 다시 쓰일 수 있기 때문에,
filter를 통해 일시적으로 걸러주었다.

📙 조합

nCr
permutation: 서로 다른 n개 중에 r개를 선택하는 경우의 수[순서 상관 X]

3C2 = 3
경우의 수: [1,2], [1,3], [2,3] => 3개

코드는 다음과 같다.

const permutation=(numbers, range)=>{
  
  let output = [];
  if(range===1) return numbers.map(num => [num]);
  
  numbers.forEach((number, index, temp)=>{
    const mainNumber = number;
    // 순열: const subNumbers = numbers.filter((_,idx) => index!==idx);
    // 순서가 상관 없어졌기 때문에, 
    // 단순히 mainNumber의 다음 값들을 subNumbers에 할당시킨다.
    const subNumbers = numbers.slice(index+1);
    
    const rePermutation = permutation(subNumbers, range-1);
    const combine = rePermutation.map(num=>[mainNumber, ...num]);
    output.push(...combine);
  });
return output;
}

📘 중복 순열

nㅠr
permutation: 중복 가능한 n개중에서 r개를 선택하는 경우의 수[순서 상관 O]

3ㅠ2 = 9
경우의 수: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2], [1,1], [2,2], [3,3] => 9개

코드는 다음과 같다.

const permutation=(numbers, range)=>{
  
  let output = [];
  if(range===1) return numbers.map(num => [num]);
  
  numbers.forEach((number, index, temp)=>{
    const mainNumber = number;
	// 같은 값을 또다시 다음 값으로 써도 상관없기에 number 할당
    const subNumbers = number;
    
    const rePermutation = permutation(subNumbers, range-1);
    const combine = rePermutation.map(num=>[mainNumber, ...num]);
    output.push(...combine);
  });
return output;
}

📌 순열/조합 빠르게 풀기

위의 코드를 어느정도 이해하고, 차이를 알 수 있다면 이를 응용해 조금 더 간단한 방법으로 코드를 짤 수 있다.

let output = [];

const cases = (numbers, range, temp = []) => {
  //3개를 선택한다는가정에 3개가 선택 됐다면 출력
  if (range === 3) output.push([...temp]);
  else {
    for (let i = 0; i < numbers.length; i++) {
      temp.push(numbers[i]);
      cases( ⭐⭐⭐ , range + 1, temp);
      temp.pop();
    }
  }
};