순열,조합 알고리즘(JS)

1.조합
n개의 물건 중에 순서를 생각하지 않고 r개를 택할 떄,
이것을 n개에서 r개를 택하는 조합이라고 하고 nCr이라고 표현한다.

예)3C2를 코드로 구현

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

조합은 순서를 상관하지 않기 때문에
[1,2]를 [2,1]로 보아도 상관이 없다.

[1,2,3]
 ^
 을 먼저 잡고 나머지 2,3에 대해서 2C1을 하면 되므로 
 이런 방식으로 재귀함수를 구성하면 된다.

코드

function combination (array, select) {
 const answer = [];
 if(select === 1) return array.map((el)=> [el]);
  //만약 추출할 개수가 1개이면 map으로 배열을 만든다.
 array.forEach((fixed,index,origin)=>{
 const rest = origin.slice(index + 1)
  //해당하는 고정점을 제외한 나머지 
 const restcombination = combination(rest,select-1)
  //나머지에 대한 조합
 const attached = restcombinations.map((el)=>[fixed,...el]);
   answer.push(...attached);
   
 
 }) 
  return answer;
}

순열은 순서 있는 조합이라고 생각하면 되는데

```javascript
function combination (array, select) {
 const answer = [];
 if(select === 1) return array.map((el)=> [el]);
  //만약 추출할 개수가 1개이면 map으로 배열을 만든다.
 array.forEach((fixed,index,origin)=>{
 const rest = [...orgin.slice(0,index),...origin.slice(index+1)]
  //해당하는 고정점을 제외한 나머지 
 const restcombination = combination(rest,select-1)
  //나머지에 대한 조합
 const attached = restcombinations.map((el)=>[fixed,...el]);
   answer.push(...attached);
   
 
 }) 
  return answer;
}

fixed 즉 고정점에 대한 관점만 바꾸면 된다.
조합에서는 오직 fixed 이후에 나머지 뒷부분만 생각했는데
순열은 fixed인 원소 빼고 나머지들이라고 생각하면 된다.
즉 fixed 앞에 있는 것들도 고려해줘야 한다.

const fixed = [...origin.slice(0,index),...origin.slice(index+1)]