중복 순열 구하기

참고 문서

• 이 블로그의 문서: DFS를 사용한 순열 구하기
• GitHub: 이 프로젝트의 리포지토리(algorithm)

이 문서의 내용

순열이란 n개의 값 중에서 r개의 값을 뽑는 모든 경우의 수를 의미합니다.

예를 들어 1, 2, 3 값 중에서 2개의 값을 뽑는 모든 경우의 수는 다음과 같습니다. 순열은 값의 중복을 배제하지 않기 때문에 1, 2 그리고 2, 1이 동시에 나타납니다.

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

중복 순열은 순열에서 중복을 허용합니다.

위의 예시를 중복 순열에 대해서 계산하면 다음과 같이 나타납니다.

[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]

재귀호출을 사용한 중복 순열 흐름도

중복 순열을 구하는 방법은 이 블로그의 문서: DFS를 사용한 순열 구하기에서 탐색 과정에서의 중복 방문 방지를 위한 visited 플래그만 제거하면 됩니다.

깊이(depth)는 0부터 시작해서 뽑으려는 수 r에 도달하면 탐색을 마치고 이전 depth로 돌아갑니다.

예시의 흐름도 depth = 2의 1, 1 1, 2 2, 1 2, 2 4개의 경우의 수가 발생합니다.

배열을 사용한 중복 순열 구현

중복 순열을 계산하기 위한 인자는 arr depth r 그리고 순열의 결과를 저장하는 out입니다.

순열에서 탐색 경로를 마킹하는 visited는 사용하지 않습니다.

depth의 초기 값은 0으로 시작합니다. r은 주어진 배열에서 몇 개의 수를 뽑아낼 것인가를 의미합니다.

protected static void duppermutation(int[] arr,
				     int[] out,
				     int depth,
				     int r)
{
	if (depth == r)
	{
		printResult(out, r);
		return;
	}
	
	for (int i = 0; i < arr.length; ++i)
	{
		out[depth] = arr[i];
		// depth를 한 칸 이동합니다.
		duppermutation(arr, out, depth + 1, r);
		// 현재 인덱스를 방문 취소하고 순열의 원소를 롤백합니다(원위치).
		out[depth] = 0;
	}
}

코드		비고
Line 6:10	if (depth == r)	depth가 r에 도달하면 하나의 경우의 수가 발생합니다.
Line 12:19	out[depth] = arr[i]	현재 인덱스의 노드를 순열에 저장합니다.
	duppermutation()	다음 depth를 진행하기 위해 재귀호출합니다.
	out[depth] = 0	새로운 순열을 찾기 위해 현재 인덱스의 노드를 원위치합니다.