순열, 조합 알고리즘

💡 순열 💡

순열 알고리즘에는 두가지 종류가 있다....중복순열과 순열이 있다....보통 순열은 몇가지의 수에서 몇가지를

골라 나열하라는 문제로 나온다. 중복이 허용되는 순열 같은 경우는 3개에서 두개를 뽑는 경우

[[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]]과 같이 처음에 택한

수에 선택한 수를 포함한 모든 배열의 수 만큼 경우의 수가 나온다(3^2). 중복이 허용되지 않는 경우에는

[[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]] 와 같이 나오게 된다. for 문을 사용해 문제를 해결할 수 있지만,

재귀를 사용해 보자....반복문이 몇중으로 겹칠 수 있으며 코드 짜기가 복잡해 진다....

---

function 순열(arr, n) { // 배열이나 숫자 중 n개를 선택하는 종류이다. 
  let res = []; // 최종적으로 합쳐져 리턴된다.
  let temp = new Array(n).fill(0) // 재귀를 돌며 채워진다. [0, 0, 0] n개씩 채워진다.
  const m = arr.length; // for문이 돌아야 하는 횟수(n개 만큼 선택 해야 하지만, 숫자는 골고루 들어가야 하니까)
  let chk = new Array(m).fill(0) // 같은 숫자가 들어가 있는지 체크하는 용도(arr의 길이만큼)
  
  function 재귀(L) {
  	if(L === n) { // level이 n과 같으면 temp의 값을 push
       res.push(temp.slice()) // temp배열의 원소를 slice해 복사한 뒤 push 해야함.
       } else {
    	for(let i = 0; i < m; i++) {
          if(chk[i] !== 1) {
          	chk[i] = 1; // 방문했다는 표시를 해 준 뒤
            temp[L] = arr[i]; // level에 배열의 값을 넣어 준다.
            재귀(L + 1)
            chk[i] = 0;	// 스택에 쌓인 재귀가 끝난 후 다시 풀어 준다 
          }
        }
    }
  }
  재귀(0)
  return res;
}
// [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]] 

---

function 중복순열(arr, n) {
  let res = [];
  let temp = new Array(n).fill(0);
  const m = arr.length; // 귀찮으면 for문 안에 넣어 줘도 된다.
  
  function 재귀(L) {
    if(L === n) {
      res = res.push(slice());
    } else {
      for(let i = 0; i < m; i++) {
        temp[L] = arr[i];
      	재귀(L + 1);
      }
    }
  }
  재귀(0)
  return res;
}
// [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]]

---

💡 조합 💡

조합은 순열에 비해 많은 조합들이 걸러진다. 예를 들어 [1,3]이 있다면 [3,1]은 허용되지 않는다.

---

function 조합(arr, n){
  let res = [];
  let temp = new Array(n).fill(0);
  const m = arr.length;
  
  function 재귀(L, idx) {
  	if(L === n) {
      res.push(temp.slice());
    } else {
      for(let i = idx; i < m; i++) {
        temp[L] = arr[i];
        재귀(L + 1, i + 1);
      }
    }
  } 	
  재귀(0, 0)
  return res;
}
// [[1,2], [1,3][2,3]]