순열 생성 알고리즘

▶순열 (순서가 있는 열)

---

 - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 

 - 순서화된 요소들의 집합에서 최선의 경우를 찾는 문제와 관련이 있다.

▶반복문을 통한 순열 생성

---

그리디하게 접근해서 바로 문제가 해결되는 경우도 있지만,

결국 모든 경우의 수를 다 따져보지 않고서는 정답을 알 수 없는 문제들이 존재한다.

그럴 때, 나올 수 있는 모든 순열을 생성하는 코드를 응용하여 문제를 해결할 수 있다.

순열 생성에 필요한 요소의 수가 고정적인 경우

간단히 반복문으로 모든 순열을 생성할 수 있다.

- 슈도코드 

 : {1, 2, 3}을 포함한 모든 순열을 생성

FOR i1 in 1->3
  FOR i2 in 1->3
    IF i2 != i1
      FOR i3 in 1->3
       IF i3 != i1 AND i3 != i2
         print(i1, i2, i3)

조건문으로  중복 선택을 막고 있다.

3개중 하나 선택하는 경우의 수 : 3

나머지 2개중 하나 선택하는 경우의 수 : 2

나머지 1개중 하나 선택 : 1

모든 경우의 수는 총

3*2*1 = 6가지

123

132

213

231

312

321

하지만 순열 생성에 필요한 요소의 수는 고정적이지 않은 경우가 많다.

필요한 횟수만큼 반복을 수행하면서 순열을 생성하려면 어떻게 해야할까?

▶재귀 호출을 통한 순열 생성

---

// arr[] : 데이터가 저장된 배열
// swap(i, j) : arr[i] 와 arr[j] 를 교환
// n: 원소의 개수, k: 현재까지 선택된 원소의 수
 
Permutation(n,k)
    IF k == n // 하나의 순열이 생성됨.
        print array // 원하는 작업 수행
    ELSE
        FOR i in k -> n-1
            swap(k,i);  // 교환을 통한 선택
            Permutation(n, k+1);  // 재귀 호출
            swap(k,i); // 이전 상태로 복귀

모든 경우의 수를 트리 형태로 표현할 수 있으므로,

트리를 순회하는 것과 같이 재귀 호출을 통해 순열을 생성할 수 있다.

트리의 단말노드에 도착하게 되면 하나의 순열이 생성된다.

SW Expert Academy의 강의를 참고하여 좀 더 이해하기 쉽도록 재구성하였습니다.

출처 : https://www.swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV2dYG86Ac0BBASw