중복 순열, 중복 조합 설명 및 코딩(JAVA)

 

전 시간에는 순열과 조합을 코딩해 보았는데 이를 기반으로 응용해서 중복 순열과 중복 조합도 만들어 볼 예정이다.

 

중복순열

---

일반 순열은 1 2나 2 3 이렇게 안겹치게 뽑는데 중복을 허용하면서 1 1, 2 2 이렇게 뽑을 수 있다. 중복 순열을 구하기 위해서는 일반 순열에서 visited배열만 제거해주면 된다.

1 2 3 4 5 라는 원소가 있을 경우 뽑을 수 있는 모든 경우이다.

순열과는 다르게 1 1 1 도 뽑히고 1 1 2 도 뽑힌다. 같은 숫자가 두개 나올 수 있게끔 visited 배열을 제거했기때문이다.

 

코드

---

package pro;

public class test17 {

	public static void main(String[] args) {
		int [] arr = {1 , 2 , 3, 4, 5};
		int r = 3;
		overLapPermu(arr, r, 0, new int[r]);

	}
	public static void overLapPermu(int[]arr , int r , int depth, int[] answer) {
		if(depth == r) {
			for(int a: answer) {
				System.out.print(a+" ");
			}
			System.out.println();
			return;
		}
		for(int i =0; i< arr.length; i++) {
			answer[depth] = arr[i];
			overLapPermu(arr , r, depth+1, answer);
		}
	}

}

 

 

중복조합

중복조합도 중복순열과 똑같이 일반 조합에서 visited 배열을 제거해주면된다.
그러면 1 1 도 뽑힐 수 있고 1 1 2 가 뽑힐수도 있다. 물론 2 1 1은 뽑히지 않는다.
start 변수를 넣는 그대로 시작하면서 visited를 제거하면 될 것 같다.

 

코드

package pro;

public class test17 {

	public static void main(String[] args) {
		int [] arr = {1 , 2 , 3};
		int r = 2;
		overLapCombi(arr, r, 0, new int[r], 0);

	}
	public static void overLapCombi(int[]arr, int r, int depth, int[] answer, int start) {
		if(depth == r) {
			for(int a : answer) {
				System.out.print(a+" ");
			}
			System.out.println();
			return;
		}
		for(int i = start; i< arr.length; i++) {
			answer[depth] = arr[i];
			overLapCombi(arr, r, depth+1, answer, i);
		}
	}

}