순열 permutation jabascript 재귀함수 이해하기

순열은 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 이다.

nPr 서로 다른 n개의 개수에서 r개를 뽑아서 순서에 상관있게 나열한다. ( permutation )

팩토리얼을 생각하면 순열은 어렵지 않다.

 

 

- 순열을 이해하기 위해서 for문과 재귀함수를 통해서 예제를 확인했다.

- for문은 이해하기 쉬웠다. N차원 배열을 생각하면 겹치는 경우의수를 제외하면 구할 수 있었다.

- 재귀함수를 통해서 구하는 방법이 이해하기가 힘들었다.

 

재귀 함수를 통해서 코드를 작성할 때에는

 

1. 재귀함수를 멈출 조건.

2. 재귀를 돌면서 변경되어야할 부분을 확인.

 

을 생각해야 했다.

 

let input = ["a", "b", "c"]; // 예제
let count = 0; // 호출 되는 경우의 수

function permutation(arr, s, r) { //(사용할 배열 이름, 시작할 위치, 시작한 위치부터 마지막 index)
  // 1. 재귀함수를 멈춰야할 조건
  if(s == r){ // s위치가 r의 인덱스까지 찾게 될때
    count++; // 호출되는 경우의수도 증가
    console.log(arr); // 배열의 상태 확인
    return;
  }
  
  // 2. 재귀를 돌면서 변경되어야 될 부분 / 메인로직
  for(let i = s; i < arr.length; i++) { // i를 0부터 시작하게 되면 같은 값도 돌 수 있기 때문에 s값 입력.
    [arr[s], arr[i] = arr[i], arr[s]] // swap s자리와 i자리를 바꾸면서 b와, c에도 접근할 수 있도록 한다.
    permutation(arr, s + 1, r) // 재귀함수를 불러서 2번째 인수는 s를 1씩 증가시킨다. r은 고정!
    [arr[s], arr[i] = arr[i], arr[s]] // 다시 원상복귀
  }
}


permutation(input, 0, 2);(사용할 배열 이름, 시작할 위치, 시작한 위치부터 마지막 index)
console.log(count); // 6

- swap을 하지 않으면 abc만 나오게 된다.

- s 와 i 를 swap을 하면서 위치를 결정하게 된다.

- s가 a자리 일때 i는 증가하면서 b와 c를 바라보고 그 값들을 스왑하면서 겹치지 않는 경우의 수들을 받을 수 있게 된다.