순열 - 재귀로 구현

수능을 본지도 어느덧 4년 전이다. 하지만, 이러한 문제유형이 아직도 기억난다. "10명 중 반장과 부반장을 뽑을 경우의 수" , "10명 중 부회장 2명을 뽑을 경우의 수"  전자는 순열(Permutations), 후자는 조합(Combination)에 대한 문제였다. 오늘은 확률과 통계 시간에 풀었던 순열을 컴퓨터적 사고를 통해 풀어보려고 한다. 시작해보자.

---

순열

nPr 는 n개 중 r개를 골라 순서를 고려해 나열할 수 있는 경우의수를 나타내는 수학 기호이다.

 

[1, 2, 3] 숫자에서 3개를 모두 써서 경우의 수를 생각해보자. ( = 3P3 = 3! = 6가지 )

(1, 2, 3) (1, 3, 2)

(2, 1, 3) (2, 3, 1) 

(3, 1, 2) (3, 2, 1)

 

이걸 작성하면서, 필자는 자연스레 앞 숫자를 1로 고정하고, 나머지 2 와 3의 순열을 생각했다.

그리고 앞 숫자를 2로 고정하고 나머지 순열, 앞 숫자 3으로 고정하고 나머지 순열 찾기를 반복했다. 

 

개수를 더 늘려보자.

[1, 2, 3, 4] 숫자에서 4개 숫자를 모두 써서 경우의 수를 생각해보자.  ( = 4P4 = 4! = 24가지 )

(1, 2, 3, 4) (1, 2, 4, 3) (1, 3, 2, 4) (1, 3, 4, 2) (1, 4, 2, 3) (1, 4, 3, 2)

... 

우선, 앞에 1을 고정하고 나머지 3개의 순열을 생각해보았다.

나머지 3개의 순열을 생각할 때도, 2를 고정하고 나머지 2개의 순열을 생각했다.

 

여기서 어떠한 규칙을 발견했는가?

한 숫자를 고정하고, 나머지들로 순열을 찾는다. (한 숫자를 고정하고 나머지들로 순열을 찾는다 ... ) 

즉, 이 규칙을 통해 우리는 순열을 재귀로 구현할 수 있는 희망을 발견하였다.

 

 

재귀로 구현하기  - 의사코드편

 

분명 의사코드인데, 코드처럼 되었다... ㅎㅎ

입력 - num (요소 개수), 출력 - 2D arr(순열, 모든 경우의 수)

const result = [];

순열Maker(elements, acc) {

  // 재귀 base
  if(elements 비어있음){
    result.push(acc);
    재귀 스탑
  }

  for(ele of elements){
      acc.push(ele); // ele 고정
      // 재귀 호출 - 쪼갤 수 있을 때까지 head, tail로 쪼개기
      순열Maker(elements(ele 제외), acc); 
    }
}

순열Maker( [ 1, 2, ... num ], [] )

 

 

재귀로 구현하기 - JavaScript 편

 

push 가 아니라 concat으로 넘겨줘야 이전 재귀 결과에 영향을 안 미치는 듯 하다.

function 순열(elements, acc){
  const result = [];
  
  function 순열Maker(elements, acc){
    if(elements.length === 0){
      result.push(acc);
      return;
    }
    elements.forEach((ele, idx)=>{
      //acc.push(ele);
      const copy = elements.slice();
      copy.splice(idx, 1);
      순열Maker(copy, acc.concat(ele));  // push 가 아니라 concat을 하는 이유는?? 복사본 넘기기?
    })
  }
  순열Maker(elements, acc);
  return result;
}


// example
순열([1, 2, 3, 4], []);

 

 

3진수로 구현하기 - 중복 순열  n파이r

 

 

to Be continue ...