반복문과 재귀식을 이용한 순열문제

서로 다른 n개의 원소 중에서 r를 중복없이 골라 순서에 상관있게 나영하는 경우의 수

반복문

let input = ["a", "b", "c"];
let count = 0;

function permutation(arr) {
  // for i => 첫번째 index 위치시킬 요소 a,b,c [i, 0, 0]
  for(let i = 0; i < arr.length; i++) {
    // for j => 두번째 index 위치시킬 요소 [i, j, 0]
    for(let j = 0; j < arr.length; j++) {
      // skip 처리
      if(i == j) continue; 
      // for k => 세번째 index 위치키실 요소 [i, j, k]
      for(let k = 0; k < arr.length; k++) {
        if(k == i) continue;
        if(k == j) continue;

        console.log(arr[i], arr[j], arr[k]);
        count++;
      }
    }
  }
}

permutation(input);
console.log(count);

재귀식

let input = ["a", "b", "c"];
let count = 0;

function permutation(arr, s, r) { //s=> 시작할 위치 r=> 몇개를 뽑을지 
  // 1. 재귀함수를 멈춰야할 조건
  if(s == r) {
    count++;
    console.log(arr);
    return;
  }
  // 2. 재귀를 돌면서 변경되어야 될 부분 /  메인로직
  for(let i = s; i < arr.length; i++) {
    [arr[s], arr[i]] = [arr[i], arr[s]]; // swap
    permutation(arr, s + 1, r); // s가 중복이 되지 않도록 s+1을 해서 다른걸 선택하게 해준다
    [arr[s], arr[i]] = [arr[i], arr[s]]; // 원상복귀
  }
}

permutation(input, 0, 2);
console.log(count);

 for(let i = s; i < arr.length; i++) 반복문에서 let i = s 인 이유는 0이 되어버리면 중복이 되기 때문이다.

[arr[s], arr[i]] = [arr[i], arr[s]]

배열의 a, b, c가 순서대로 들어가게 해주어야 하는데 arr를 고정시키고 s + 1 이기 때문에 1부터 돌게되는데 

a 말고 b, c에도 접근을 해야하기 때문에 내가 선택한 위치의 idx가 s로 들어오게 된다.

 

풀이

s = 0, r = 2, i = 0  swap을 해도 똑같다 [a,]

 permutation(arr, s + 1, r) 다시 재귀함수 호출을 하게 되고 s = 0 + 1 이 된다.

s = 1, r = 2 [a,b,]

s = 2, r = 2 [a,b,r] => [a,b,c]

...

다시 원상 복귀 시키고 i는 for문에 의해서 i++ 증가하게 된다.

s = 1, r = 2, i = 2 

1은 "b" 이고 2는 "c"이다. 이 둘은 swap 하게 되고 위치가 바뀌어 [a, c,]가 된다.

s = 2, r = 2 [a, b, c]

(원상복귀) s = 1, r = 2, i = 2 [a, b, c]

i++ 으로 증가하여 3이 되지만 i < arr.length 의 조건에 맞지않아 종료가 된다.

...

이전 재귀로 back (첫번째 요소를 다시 선택하기 위하여) 

그렇게 되면 i는 다시 0이 되고 원상복귀 과정을 거친 후에 i++ 이기 때문에 i는 1이 된다.

s = 0, r = 2 i = 1 [b, a, c]