자바스크립트로 조합,순열 구현하기

조합을 구하는 방법

[1,2,3,4]로 3개를 뽑는 조합을 만드는 방법을 생각해보면,

1을 선택하고 나머지 [2,3,4]중에서 2개를 뽑는 조합을 구한다
-> [2,3],[2,4],[3,4] 임. 여기에 1을 붙여준다.
[1,2,3],[1,2,4],[1,3,4]

2를 선택하고 나머지 [3,4]중에서 2개뽑는 조합을 구한다.
-> [3,4]임 여기에 2을 붙인다.
[2,3,4]

3을 선택하고 나머지 [4]중에서 2개뽑는 조합을 구한다.
->[]

4을 선택하고 나머지 []중에서 2개뽑는 조합을 구한다.
->[]

종료
[1,2,3],[1,2,4],[1,3,4],[2,3,4] :4가지

배열([1,2,3,4])을 순회하면서 하나씩 고정시키고 그 뒤에있는 나머지 원소들가지고 다시 재귀적으로 조합을 구해서 붙이면 된다.

재귀로 나타내보기

재귀함수는 종료조건이 중요하다! 종료 조건이 없다면 무한루프처럼 스택이 계속 쌓여서 콜스택이 터지기 때문!

재귀 종료 조건: 하나를 선택할 때에는, 모든 배열의 원소를 선택해서 리턴한다

const getCombinations=(arr,selectNumber)=>{
  //arr은 조합을 구할 배열, selectNumber: 몇개를 뽑아서 조합을 구할건지
  const result=[];
  if(selectNumber===1){
    // 1개의 원소를 선택할때는 ex) A,B,C,D중 한개 선택
    // [[A],[B],[C],[D]] 경우 밖에 없음
    return arr.map((a)=>[a]);
  }
  arr.forEach((fixed,index,origin)=>{
    const rest=origin.slice(index+1);//현재 인덱스 뒤에것부터 원본 배열의 끝까지 잘라서 나머지 배열을 만듬
    const combinations=getCombinations(rest,selectNumber-1); //나머지배열에 대해서 조합을 구한다
    const attached=combinations.map((el)=>[fixed,...el]);
    //나머지배열에대해서 구한 조합에, 고정할 원소 하나를 맨 앞에 넣어준다
    result.push(...attached)
  });
  
  return results;
    

순열 구하기

조합으로부터 도출해낼 수 있다.

const getPermutations=  (arr, selectNumber)=> {
  const results = [];
  if (selectNumber === 1) return arr.map((a) => [a]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열 
    const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
    const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
    results.push(...attached); // 배열 spread syntax 로 모두다 push
  });

  return results; // 결과 담긴 results return
};