[Java Algorithm Note] 순열 (feat. 재귀)

순열, 조합, 부분집합 이 세가지에 대해서 중요하게 생각을 못했는데,

이번에 배워보니 정말 너무너무 중요한 것들이어따..!!

이것들을 공부하고나니 문제에서도 다양하게 활용할 수 있음

그래서 오늘은 그 중 첫 번째로 순열을 구현하는 방법에 대해 정리해보려한다.

 

📎 순열

순열은 서로 다른 n개의 원소에서 r개를 순서에 상관있게 선택 혹은 나열하는 것을 말한다.

 

예를 들어 {1, 2, 3}의 배열이 있다고 하면,

{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, ... 이런 식으로 나열되는 것!

 

여기서 중요한 점은 {1, 2, 3}과 {3, 2, 1}이 서로 다르다는 것이다.

기본 순열은 중복은 허용하지 않지만 순서를 가지기 때문에 순서가 다르면 다른 순열로 본다.

 

중복이 존재하는 수열도 있는데, 이는 중복 수열이라고 한다.

중복 순열은 {1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 1}, ... 과 같이 중복을 허용한다.

 

👉 정리하자면,

기본 순열은 중복은 허용하지 않고 순서만 있고,

중복 순열은 중복과 순서가 모두 있는 순열!!

---

📎 기본 순열 구현

public class Permutation1 {
	
	static char[] src = { 'a', 'b', 'c', 'd' };

	/*
     * 기본 순열 - 중복 X, 순서 O
     * @param nth - 몇 번째 선택인지 표현
     * @param choosed - 선택된 요소
     * @param visited - 사용된 적 있는 요소들 기록
     */
	static void makePermutation(int nth, char[] choosed, boolean[] visited) {
    	if(nth == choosed.length) { // 기저 조건: choosed를 다 채웠다면 끝
    		System.out.println(Arrays.toString(choosed));
    		return;
    	}
    	
    	for(int i = 0; i < src.length; i++) {
    		if(!visited[i]) {
    			visited[i] = true; // 해당 요소 선택되었음을 기록 (중복 방지를 위함)
    			choosed[nth] = src[i]; // 해당 요소 선택하기
    			makePermutation(nth+1, choosed, visited); // 몇 번째 선택인지 카운트, 선택된 요소 true로 바뀐 visited 함께 넘겨주기
    			visited[i] = false; // 해당 요소를 다시 false로 바꿔주어 다음 순열에서는 사용할 수 있게 해주기
    		}
    	}
    }
	
	public static void main(String[] args) {
        System.out.println("순열");
        makePermutation(0, new char[3], new boolean[src.length]); // src에서 3개를 뽑아 만들 수 있는 순열을 모두 출력
	}

}

nth 파라미터를 이용하여 현재의 요소 선택이 몇 번째인지를 표현하고,

choosed에는 현재 선택한 요소를 담아서 순열을 완성시킬 수 있게 했다.

visited는 중복을 피하기 위해 사용했다.

---

📎 중복 순열 구현

public class Permutation2 {
	
	static char[] src = { 'a', 'b', 'c', 'd' };
	
	/*
     * 중복 순열 - 중복 O, 순서 O
     * ex) abc aab --> 중복 순열
     * 기본 순열에서 visited만 빼주면 ok
     * 
     * @param nth - 몇 번째 선택인지 표현
     * @param choosed - 선택된 요소
     */
	static void makePermutationDup(int nth, char[] choosed) {
    	if(nth == choosed.length) { // 기저 조건: choosed를 다 채웠다면 끝
    		System.out.println(Arrays.toString(choosed));
    		return;
    	}
    	
    	for(int i = 0; i < src.length; i++) {
    		choosed[nth] = src[i]; // 해당 요소 선택하기
			makePermutationDup(nth+1, choosed); // visited 기록 필요 없이, 몇 번째 선택인지만 카운트 해주면 ok
    	}
    }
	
	public static void main(String[] args) {
        System.out.println("순열");
        makePermutationDup(0, new char[3]); // src에서 3개를 뽑아 만들 수 있는 중복 순열을 모두 출력
	}

}

중복 순열은 기본 순열과 거의 동일한데,

중복을 허용하므로 visited 배열만 빼주었다.

---

👀 정리

순열은 중복 없이 요소들을 뽑아 나열한 것을 의미하고,

중복 순열은 중복을 허용하여 요소들을 뽑아 나열한 것을 말함

순열과 중복 순열은 모두 재귀 방식으로 간단히 구현할 수 있는데,

순열 구현 메서드에서 visited 배열만 제거해주면 중복 순열이 된다.