[알고리즘] 조합, 순열, 중복순열

 

조합, 순열, 중복순열은 모두 같은 로직으로 진행한다.

 

배열에서 3개를 선택하는 경우 1. 하나의 수를 선택한다. 2. 3개를 뽑는 순열 중 하나의 수를 선택했으니 남은 배열에서 2개를 선택해야한다. 3. 남는 배열에서 1개를 선택할 때 까지(재귀 탈출 조건) 2번 과정을 재귀적으로 반복한다.

 

이 세 과정을 반복하면 조합, 순열, 중복순열을 구할 수 있다.

조합, 순열, 중복순열들은 서로 남은 배열을 설정해주는 과정에서 차이가 있다.

 

알고리즘에 잘 적용 해보자!

 

조합

function combination(arr, n, bucket){
    if(n===0){ // 탈출조건
      result.push(bucket)
      return;
    }
    for(let i=0; i<arr.length; i++){ // 조합은 순열과 다르게 순서가 달라도 같은 것으로 취급
      let pick = arr[i]
      let rest = arr.slice(i + 1) // 그래서 arr 배열을 하나씩 줄여나가 주는 것
      combination(rest, n-1, bucket.concat(pick)) // 재귀
      //push가 아닌 concat을 사용해야하는 이유는 bucket의 원본 배열에 변화를 주지 않기 위함
    }
    return result
  }

 

순열

function permutation(arr, n, bucket){
    if(n === 0){ // 탈출조건
      result.push(bucket)
      return;
    }
    for(let i=0; i<arr.length; i++){
      let choice = arr[i] // 하나를 초이스
      let rest = arr.slice() // 얕은 복사
      rest.splice(i, 1) // 순열식이니까 초이스한 값을 제외
      permutation(rest, n-1, bucket.concat(choice)) // 재귀
      //push가 아닌 concat을 사용해야하는 이유는 bucket의 원본 배열에 변화를 주지 않기 위함
    }
    return result
  }

 

중복순열

 function multiPermutation(arr, n, bucket) {
    if(n === 0) { // 탈출조건
     result.push(bucket);
     return;
    }
      for(let i = 0; i < arr.length; i++){
      multiPermutation(arr, n - 1, bucket.concat(arr[i])) // 재귀
      //push가 아닌 concat을 사용해야하는 이유는 bucket의 원본 배열에 변화를 주지 않기 위함
    } 
  }