[Algorithm] 순열 Permutation

알고리즘 문제를 풀다보면 리스트내의 데이터로 여러 조합을 만들 경우가 있고
이럴 때, 중복 여부, 순서 상관 여부에 따라 다르게 계산해야 한다.

순열 Permutation

순서를 다르게 취급한다면
nPr = n개의 숫자에서 r개를 뽑아 정렬하는 가짓수이다.
{1,2,3}이 있다면, 여기서 2개를 뽑아 정렬할 때
n=3, r=2 -> 3P2가 된다.

출력해보면
{1,2}, {2,1}
{1,3}, {3,1}
{2,3}, {3,2}
순서도 고려하기에 {1,2}와 {2,1}은 다르게 취급한다.

코드로 알아보자.

중복을 허용하는 순열

class Main {

	public static void main(String[] args) {

		List<String> arr = new ArrayList<>();
		arr.add("a");
		arr.add("b");
		arr.add("c");

		List<String> result = new ArrayList<>();
		reculsion(arr, result, arr.size(), 2);

	}

	/**
	 * 순열 구하기
	 * 
	 * arr    : 기준 리스트
	 * result : 결과를 담아줄 리스트
	 * n      : 전체 갯수
	 * r      : 뽑을 갯수
	 */
	private static void reculsion(List<String> arr, List<String> result, int n, int r) {

		if (r == 0) { //4️⃣
			System.out.println(result.toString());
			return;
		}

		for (int i = 0; i < n; i++) {
			result.add(arr.remove(i)); //1️⃣, 3️⃣, 
			reculsion(arr, result, n - 1, r - 1); //2️⃣ 
			arr.add(i, result.remove(result.size() - 1)); //5️⃣
		}
	}
}

위와 같은 메인 코드가 있고 하나씩 뜯어 생각하자.
우선, 순열을 구하는 reculsion함수는 파라미터로
[기준 리스트, 결과 리스트, 전체 갯수, 뽑을 갯수] 이렇게 4개를 받는다.

1️⃣ 하나를 뽑아서 결과에 넣는다.
기준 리스트에서 i번째 값을 지우고 그 값을 결과 리스트에 넣는다.

result.add(arr.remove(i));

2️⃣ 결과 리스트에 넣는 값과 상관없이 남은 데이터 중 하나를 뽑아야 함으로 재귀 호출을 해준다.
기준 리스트에서 데이터가 하나 빠지고 결과 리스트로 들어갔기에 하나씩 -1해주고 호출한다.

reculsion(arr, result, n - 1, r - 1);

3️⃣ 재귀 호출에서는 다시 첫 원소를 결과 리스트에 넣는다.
이 과정은 1️⃣ 번과 동일하다.⬆️

4️⃣ 그 다음 재귀호출은 1개 중 0개를 뽑게 됨으로 탈출문에 들어간다.

if (r == 0) {
	System.out.println(result.toString());
	return;
}

5️⃣ 재귀함수에서 탈출하면 결과 리스트에 있던 것을 다시 원본 리스트로 옮겨준다.
제일 최근에 빠진 원소는 결과 리스트의 가장 마지막에 있기에 마지막꺼부터 넣어준다.
result.size()-1 이 결과 리스트의 마지막 항목이다.

arr.add(i, result.remove(result.size() - 1));

이러면 for문을 한번 돌게 된 것이다.🤪

6️⃣ 반복문에 의해서 2번째 데이터에 재귀함수를 적용한다.
i가 0이 아니라 1이 되었을 것이다. 그러니 2번째 데이터를 가지고 재귀를 적용시키는 것이다.

for (int i = 0; i < n; i++) {
	result.add(arr.remove(i)); 
	reculsion(arr, result, n - 1, r - 1);
	arr.add(i, result.remove(result.size() - 1));
}

7️⃣ 위의 로직이 반복 된다. 1️⃣ 부터 5️⃣ 까지를 1번 하는게 for문을 한번 도는 경우이고
for문은 기준 리스트의 사이즈 = n 만큼 돌게 된다.

중복이 없을 경우의 순열

private void permutation(List<Integer> nums, int[] result, int depth, int n, int r) {

	if (depth == r) {
		System.out.println(Arrays.toString(result));
		return;
	}
	
    	for (int i = 0; i < n - depth; i++) {
		result[depth] = nums.remove(i);
		permutation(arr, nums, result, depth + 1, n, r);
		nums.add(i, result[depth]);
	}
}

depth를 찾은 만큼 배열의 문자가 빠지기에 반복문은 전체 갯수 n에서 찾은 갯수(빠진 갯수) depth만큼만 돌려준다. 재귀함수를 호출할 때는 depth만 하나씩 늘려준다.
이렇게 하면 굳이 결과를 리스트에 넣고 빼고 하지 않아도 된다.
result[depth] 의 값만 계속 바꿔줄 수 있다.

위의 경우를 그림으로 자세히 이해해보자.

1. depth = 0에서 첫 인덱스의 값을 선택하고, 모든 인덱스를 돌면서, (1,1),(1,2),(1,3)을 swap 해준다. (자리를 바꿔준다.)

2. depth = 1에서 두 번째 인덱스를 선택하고, 두 번째 인덱스와 마지막 인덱스의 값을 swap 해준다.

3. depth = 2에서 마지막 인덱스와 마지막 인덱스를 swap해준다.

4. depth = 3에서 depth==r(뽑으려는 갯수) 같기에, 해당 값을 출력한다.