순열은 앞서 살펴봤던 visited를 이용하는 방식이외에도 여러 가지 방식으로 작성이 가능하다. 여기서는 swap 을 이용해서 순열을 구하는 방식에 대해 살펴보자. 기본적인 컨셉은 아래와 같다. - swap: 요소와 요소의 위치를 서로 변경한다. - depth: 선택할 수 있는 요소의 범위를 조절한다. 진행 과정 먼저 최초의 배열 {A, B, C, D}가 있고 depth 0에서 swap 되는 단계는 다음과 같을 것이다. 물론 depth0-1인 BACD는 depth0-0 인 ABCD에 대한 모든 하위 depth가 종료된 후 진행될것이다. 이제 depth0-0의 하위인 depth1의 동작을 살펴보자. 첫 번째 자리는 A로 고정된 상태에서 나머지 요소들이 swap 대상이 된다. 이제 depth1-0이 종료되면..

앞선 포스트에서 살펴봤듯이 순열을 구현하기 위해 필요한 개념은 3가지이다. 1. 순서대로 나열 - 반복문을 통해 순차적으로 접근한다. 2. 중복을 허용하지 않음 - 이미 사용한 요소가 무엇인지 저장해놓는다. 이를 위해 visited라는 이름의 배열을 사용한다. 3. 재귀를 통한 접근 - 선택해야할 요소들을 하나씩 줄여가면서 자신 호출 4개의 원소를 가진 배열을 만들고 여기서 3개를 선택해서 나열하는 경우의 수를 조사해보자. private static char[] src = {'A', 'B', 'C', 'D'}; 기본적인 코드의 흐름은 다음과 같다. 코드에 대한 설명은 주석으로 대체한다. /** * 순열을 만들고 출력하는 메서드 * @param r 선택할 요소의 개수 * @param current 현재 선..

순열의 정의 순열(Permutation)이란 n개의 원소에서 r개를 중복을 허용하지 않고 선택해서 순서대로 늘어놓은 것을 말하며 nPr이라고 표기한다. 순열의 전개 과정 4개의 원소 {1,2,3,4}에서 3개를 선택해서 순서대로 나열하는 방법에 대해 생각해보자. 맨 처음은 4개의 원소가 모두 올 수 있다. 그 다음은 각 경우에 대해 중복을 허용하지 않으므로 1st에서 선택되지 않은 3녀석이 각각 올 수 있다. 즉 4*3 가지가 가능하다. 여기서 1-4와 4-1은 당연히 다르다. 우리는 순서대로 나열하고 있다는 점이 중요하다.(만약 순서가 상관 없이 뽑기만 진행한다면 조합이 된다.) 동일한 절차를 거치면 우리가 원하는 순열을 얻을 수 있다. 드디어 모든 절차가 끝났고 4개의 원소에서 중복 없이 3개를 선택..

1