-
[Java]중복 순열(Permutation with repetition)Algorithm/완전 탐색 2021. 2. 18. 14:13
*중복 순열(Permutation with repetition)
->순열을 이해했다면, 중복 순열은 이해하기 쉽다. 순열을 먼저 이해하도록 하자.
[Java] 순열(Permutation)
*순열(Permutation) -> 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는 것을 말한다. Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 순열을 구하시오라고 하면, 결과는 {123, 132, 213, 231,
sskl660.tistory.com
->중복 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는데 일반 순열과 다르게 집합의 원소를 중복해서 선택할 수 있는 차이가 존재한다.
Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 중복 순열의 결과는 {111, 112, 113, 121, ..., 333} 총 27가지 경우의 수가 나온다.
중복 순열 경우의 수 ※ 중복 순열이 총 27가지가 나오는 이유는, 순열과는 다르게 다음 수를 선택할때 중복 선택을 허용하기 때문이다.
-> 위의 중복 순열의 경우의 수를 일반화하면, n개의 수 중 r개를 선택하는 중복 순열은 n의 r승개의 경우의 수를 가짐을 알 수 있다.
중복 순열 경우의 수 *구현(Java)
-> 순열과 마찬가지로 재귀를 이용하면 쉽게 구현할 수 있다. 중복 선택할 수 있다는 점만 다르다는 것을 기억하면 된다.
※ 중복 순열 알고리즘
1. 대상 집합을 순회하며 숫자를 하나 선택하고, 자신의 메서드를 재귀 호출한다.
2. 선택된 숫자가 r개가 된다면, 재귀를 종료한다.
-> 예를 들어, 1부터 3까지의 자연수 3개 중 2개를 선택한 중복 순열은 다음과 같이 구현할 수 있다. 일반 순열에서 중복 선택을 방지하기 위해 만들었던 visited배열과 관련 로직이 사라진 것을 확인할 수 있다.
package cases; import java.util.Arrays; public class Permutation_with_repetition { // 선택하고자 하는 대상 집합. static int[] target = new int[] { 1, 2, 3 }; // 대상 숫자를 담아둘 배열을 만든다. static int[] result = new int[2]; public static void main(String[] args) { permutation(0); } // 순열 메서드(cnt는 선택 횟수) private static void permutation(int cnt) { // 2개를 선택했으므로, 결과를 출력하고 재귀를 종료한다. if (cnt == 2) { System.out.println(Arrays.toString(result)); return; } // 대상 집합을 순회하며 숫자를 하나 선택한다. for (int i = 0; i < 3; i++) { // 숫자를 담는다. result[cnt] = target[i]; // 자신을 재귀 호출한다. permutation(cnt + 1); } } }
'Algorithm > 완전 탐색' 카테고리의 다른 글
[Java]다음 순열(Next Permutation) (0) 2021.02.25 [Java]부분 집합(Subset)과 멱집합(Power Set) (0) 2021.02.25 [Java]중복 조합(Combination with repetition) (0) 2021.02.18 [Java]조합(Combination) (0) 2021.02.18 [Java]순열(Permutation) (0) 2021.02.18