js 순열 조합

조합

서로다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때, 이것은 n개에서 r개를 택하는 조합이라 하고 기호로 nCr 같이 나타낸다.
예를들어 3C2을 구현한다면

입력:[1,2,3]
출력:[1,2],[2,3],[1,3]

와 같이 가지게 된다 3개중에 2개씩 선택할 때 나올 수있는 모둔 조합을 구한다 이 때 조합의 순서는 상관이 없다 [1,2],[2,1]은 같기때문에 하나의 조합으로 취급한다는 얘기

수도코드

1을 선택하고 ->나머지 [2,3] 중에서 1개씩 조합을 구한다.
2를 선택하고 -> 나머지[3] 중에서 1개씩 조합
3을 선택하고 -> 나머지[] 중에서 1개씩 조합
끝

배열의 처음부터 하나씩 선택 하면서 뒤에 배열들을 붙여나가면 조합을 구하는 것이다. 중복을 채택하지 않기때문에 [1] 고정 [2,3] 선택 이후 [2] 선택을 했다면 [1] 은 이미 선택 했기때문에 배제하고 진행한다.
'나머지'에 대해서 구할때는 재귀함수를 사용하는것이 좋을것이다. 계속해서 반복 될 일 을 구해놓고 들어가는 인자를 바꾸어주기만 하면되기 때문

풀이과정

재귀를 사용한 조합 풀이방법

1. 재귀 종료 조건: 멈추고 싶은 nCr r<-에 맞추도록한다 예컨데 nC3이라고 한다면 3에 도달하는순간 멈추면 될것이다.

2. 고정된 값의 나머지 배열에 대해서 조합을 구한다 [1] 고정 [2,3] 나머지 가 된다.

3. 조합 결과([2,3] 중에 1개 선택)에 고정된 값을 앞에 붙여 리턴할 배열에 전개 구문으로
   으로 배열화

4. 2C3 과같이 선택하려는 개수가 많으면 빈 배열이 return 되기 때문에 위의 예에서 3을 선택할 때에는 빈 배열이 돌아와 포함되지 않는다.

코드

nC3을 구하는 조합

   const getCombination=(arr,num)=>{
            const result = [];//핵심 포인트 구하고자하는 배열을 내부에 넣어 값을 매번 초기화 시켜줘 원하는 값 4c2, 3c2 든 내보낼수있다.

  
   if (num === 1) return arr.map((el) => [el]);      
     //n개중에서 3개 선택할때 num 초기값 3 으로시작해서 num-1 을 해가고 1도착
        
        
    arr.forEach((fixed, index, origin) => {
      //+1을해서 fixed를 제외 하고 한칸씩 앞으로 가서 중복방지
      const rest = origin.slice(index + 1); 
        
//재귀 fiexed가 제외된 나머지가 들어가서 [2,3] =>[3] =>[] 줄어가다가 재귀종료조건 return
   const combinations =  getCombination(rest, num - 1); 
        
        
         const attached = combinations.map((el) => [fixed, ...el]);
      result.push(...attached); 
    });            
                        return result; 

        
  }
   getCombination(number,3)
   


    return answer;
}

순열

서로 다른 n개의 물건 중에서 r개를 택하여 한 줄로 배열 하는것을 n개의 물건에서 r개 택하는 순열이라 하고, nPr 와 같이 나타낸다 조합은 '순서'에 상관없이 선택한 것이라면, 순열은 순서가 중요하다.

입력:[1,2,3]
출력:[ [1,2],[1,3],
[2,1],[2,3],
[3,1],[3,2] ]

수도코드

재귀 종료의 조건은 조합 함수와 동일하다.

1 고정 나머지 [2,3] 2고정 [1,3] 3고정 [1,2] -> 조합과는 다른점은 지워나가지 않는다는 점이다.

코드

nP2

const getPermutation = (arr,num) =>{

const result = [];
if(num ===1){
return arr.map((el)=>[el])

}

arr.forEach((fixed,index,origin)=>{

  const rest = [...origin.slice(0,index),...origin]
//fixed를 제외한 나머지 전부
  const permutation = getPermutation(rest,num-1);
  
  const attached = permutation.map((el)=>[fixed,...el])
  
  result.push(...attached)

})
return result


}
getPermutation([1,2,3],2)


}