순열과 조합

소수만들기 문제를 풀다가 고민에 빠졌는데
이게 경우의 수를 만드는 방식에 따라서 답이 갈린다는 이야기를 봤다.

그리고 이게 먼 개소리지! 하고 찾아보니까

경우의 수를 만드는 방법에는 두가지가 있다는 것을 알아냈다.

아마도 고등학교때 나왔던 것 같은데 바로 순열과 조합이다.

아니 근데 이걸 알아야하나 그냥 set으로 중복 지우면 그만인데ㅠㅠ

순열 먼저!

const arr = [1,2,3,4,5]
let sum = []
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(i !== j && i !== k && j !==k){
          console.log(arr[i]+arr[j]+arr[k])
        }
      }
    }
  }

순열이란, 순서에 상관 없이 모든 경우의 수를 뜻한다.
간단하게 설명하면 [1,2,3]과 [3,2,1]은 다른 수라는 의미를 가지고 있다.

흔히 생각하는 내가 쓸 수 있는 숫자는 5개
사용할 수 있는 공간은 3개라고 하면

첫번째는 모든 숫자를 사용할 수 있으니까 5개
두번째는 첫번째에서 고른 숫자를 사용할 수 없기에 4개
세번째는 첫번째, 두번째에서 고른 숫자를 사용할 수 없기에 3개 이기에

5x4x3해서 60이라는 경우의 수를 찾아낼 수 있다.

이번에는 조합!

const arr = [1,2,3,4,5]
let sum = []
len = arr.length;
  for (let i = 0; i < len - 2; i++) {
    for (let j = i + 1; j < len - 1; j++) {
      for (let k = j + 1; k < len; k++) {
        console.log(nums[i] + nums[j] + nums[k])
      }
    }
  }

조합은 순서가 관계가 있는 경우의 수를 뜻한다.
쉽게 말하면 [1,2,3][1,3,2] [3,2,1]이 3개가 같은 것으로 판단한다.

그래서 순열의 값에서 중복이 될 수 있는 수를 빼면 되는데
쉽게 생각을 하면 만약 3개를 골라야하면 3!이 된다.

5가지의 경우의 수가 있고, 3개를 골라야하는데 조합으로 계산을 할 경우
5x4x3/3!해서 10이 나온다.

솔직히 잘 이해는 안되는데 뭔가 꾸겨넣고 있다.

지금 저 위가 문제가 되는 이유는 수량의 갯수가 많아질 경우다.
5개중 3개를 골라야하기 때문에 반복문이 3개가 필요한데

100개를 골라야한다면 반복문이 100개가 필요하게 될 것이다.

이래서 재귀함수의 형식으로 만들어야하는데.......
아직 내 머리속으로 이해가 안되서 이번주내로 이곳저곳의 코드를 참고해서 내가 알기 쉽게 구성을 해놓으려고 한다 ㅠ_ㅠ