더보기
순열이란 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;
}
}
코드 | 비고 | |
현재 인덱스의 노드를 |
||
'Algorithm > Algorithm patterns' 카테고리의 다른 글
DFS를 사용한 순열 구하기 (0) | 2023.12.06 |
---|---|
Swap을 사용한 순열 구하기 (0) | 2023.12.06 |
너비 우선 탐색(BFS, Breadth-First Search) (0) | 2023.12.05 |