알고리즘_순열

순열이란💡

모든 경우의 수를 계산 하는 알고리즘이다.

ex)[1,2,3]이라는 배열이 주어졌을때, 이 배열의 요소들을 모두 사용하여 만들 수 있는 경우의 수는 아래와 같다.
//
//
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 총 6개.
이는 3!의 값과 동일한 개수이다

순열의 종류💡

1. 순열

위의 예시에서 보여줬던 형태의 순열이다.
보통 주어진 요소들로 만들어낼 수 있는 모든 경우의 수 또는, 주어진 요소들 중 특정 개수만을 뽑는 경우의 수를 만들때 사용된다.
아래 예시를 통해 알아보자.

예시)요소와, 개수가 주어졌을 때 만들어 낼 수 있는 경우의 수
➡️주어진 포커카드(arr)중 num개를 골라 만들수 있는 모든 경우의 수를 반환하는 함수를 작성하시오.

*본인은 순열을 생성해주는 함수를 하나 생성후(permutation) ,
함수내부(makePokerCase)에서 호출 하는 방식으로 코드를 작성하였다.

function makePokerCase(arr,num){ 
const result = [] //재귀함수가 끝난후 result 
const permutation = function(arr,bucket,num){
 // arr => 주어진 요소들, bucket=>각 경우의 수를 담는 배열(기본적으로 빈배열로 설정), num=> 원하는 개수
if(num === 0){
  result.push(bucket);
  return;
}
//재귀 함수의 탈출 조건

for(let i = 0; i<arr.length; i++){
let el = arr[i];
// 반복문마다 arr의 요소들을 하나씩 el에 할당.
sliceArr = arr.slice()
// 원본 배열에는 영향이 가지 않게 하기위해 얕은복사 실행
sliceArr.splice(i,1);
// 사용한 요소는 제거
permutation(sliceArr,bucket.concat(el),num-1)
// 1.아직 사용되지 않은 요소들로 이루어진 배열로 다시 permutation함수 호출
// 2.이때 bucket에는 사용된 요소가 담긴다.
// 3.num도 한개씩 줄여가면서,num이 0이 되었을때는 첫번째 반복문의 값이 result 에 담기고
// 4.다음 반복문이 실행 
// 5.모든 반복문이 다 실행되면, result 에는 경우의 수가 담겨있게 된다.
   }
}
permutation(arr,[],num)
  return result
}

2.중복순열

중복순열이란, 요소와 개수가 주어졌을때 중복을 허용하며 만들수 있는 경우의 수를 만들때 사용한다.
아래 예시를 통해 알아보자.

예시) 요소와, 개수가 주어졌을 때 중복을 허용하며 만들어 낼 수 있는 경우의수
➡️ 가위바위보 게임은 2인 이상의 사람이 동시에 '가위, 바위, 보'를 외치고 동시에 가위, 바위 또는 보 중에서 한 가지를 의미하는 손 모양을 내밀어 승부를 결정짓는 게임입니다. 세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 세 번의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성합니다.

*이문제 또한 순열을 생성해주는 함수를 하나 생성후(rpsFunc) ,
함수내부(rockPaperScissors)에서 호출 하는 방식으로 코드를 작성하였다.

function rockPaperScissors (count) {
  let arr = ['rock','paper','scissors']
  let result = []
  if(!count){
    count = 3
  }
  // count변수에 할당이 되지 않았을때는 기본으로 3판을 한다고 가정한다.
  // 만약 count변수에 수가 할당이 되면 그 수만큼 가위바위보를 한다.
  let rpsFunc = function(round,bucket){
    for(let i = 0; i<arr.length; i++){
      if(round === 0){
      result.push(bucket)
      return;
  }
  // 재귀함수 탈출조건
  rpsFunc(round-1, bucket.concat(arr[i]))
 }
}
rpsFunc(count,[])
return result
}

이렇게 순열의 두가지 종류를 예시를 통하여 알아보았다.
실제로 중복순열이 얼마나 쓰일지는 모르겠지만, 알아두는 것이 좋으니 잘 알아두도록 하자.
일반순열의 경우 permutation 함수를 재호출 할때 num을 -1 씩 하는것과,
기존 배열에 영향이 가지 않게 얕은복사(slice), 사용한 요소는 제거하기(splice) 이 3가지의 포인트가 굉장히 중요하다고 느꼈다.