[알고리즘] 자바 순열, 중복순열, 조합, 중복조합 재귀로 구현하기

1️⃣ 순열

• 서로 다른 n개중에 r개를 선택하는 경우의 수
• 순서 O
• 경우의 수 : n! / (n-r)!

// 순열
public static void permutation(ArrayList<Integer> list, int count) {
    // 다 뽑았을 때
    if (count == 0) {
        System.out.println(list);
        perCount++;
        return;
    }

    for(int i = 0; i < n; i++) {
        if(list.contains(arr[i])) {
            continue;
        }
        list.add(arr[i]);
        permutation(list, count - 1); // 뽑을 때 마다 count - 1
        list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
    }
}

arr 가 {1,2,3,4} , r = 2로 주어졌을 때

서로 다른 n개를 뽑기 위하여 list에 이미 포함되어 있을 경우 넣지 않는다.

4! / (4-2)! = 12를 만족한다.

 

2️⃣ 중복순열

• n개중에 r개를 선택하는 경우의 수 (중복 허용)
• 순서 O
• 경우의 수 : n^r

// 중복순열
public static void dupPermutation(ArrayList<Integer> list, int count) {
    // 다 뽑았을 때
    if (count == 0) {
        System.out.println(list);
        dupPerCount++;
        return;
    }

    for(int i = 0; i < n; i++) {
        list.add(arr[i]);
        dupPermutation(list, count - 1); // 뽑을 때 마다 count - 1
        list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
    }
}

arr 가 {1,2,3,4} , r = 2로 주어졌을 때

n개를 뽑기 위하여 순열과 다르게 중복이 허용되므로 list에 이미 포함되어 있을 경우를 고려하지 않고 전체탐색한다.

4 * 4 = 16을 만족한다.

 

3️⃣ 조합

• 서로 다른 n개중에 r개를 선택하는 경우의 수
• 순서 X
• 경우의 수 : n! / r!(n-r)!

// 조합
public static void combination(ArrayList<Integer> list, int index, int count) {
    // 다 뽑았을 때
    if (count == 0) {
        System.out.println(list);
        comCount++;
        return;
    }

    for(int i = index; i < n; i++) {
        list.add(arr[i]);
        combination(list, i + 1,count - 1); // 뽑을 때 마다 count - 1
        list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
    }
}

arr 가 {1,2,3,4} , r = 2로 주어졌을 때

조합의 경우 순서를 고려하지 않으므로 뒤에서 한 탐색을 다시 할 필요가 없으므로 탐색할 때 위치를 저장하여 index 기준으로 탐색한다.

또한 중복을 허용하지 않으므로 뽑을 때마다 index를 증가시켜준다.

 

4! / 2!(4-2)! = 6을 만족한다.

 

4️⃣ 중복조합

• n개중에 r개를 선택하는 경우의 수
• 순서 X
• 경우의 수 : (r + (n - 1))! / r!(n - 1)!

// 중복조합
public static void dupCombination(ArrayList<Integer> list, int index, int count) {
    // 다 뽑았을 때
    if (count == 0) {
        System.out.println(list);
        dupComCount++;
        return;
    }

    for(int i = index; i < n; i++) {
        list.add(arr[i]);
        dupCombination(list, i,count - 1); // 뽑을 때 마다 count - 1
        list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
    }
}

arr 가 {1,2,3,4} , r = 2로 주어졌을 때

조합과 동일하지만 중복을 허용하므로 뽑을 때마다 index를 증가시키는 부분을 없애준다.

(2 + (4 - 1))! / 2! (4 - 1)! = 5! / 3!2! = 10을 만족한다.

 

전체코드

import java.util.ArrayList;

public class Test{
	static int[] arr; // 뽑을 기준 배열
	static int n; // 기준 배열 길이
	static int perCount; // 순열 갯수
	static int dupPerCount; // 중복순열 갯수
	static int comCount; // 조합 갯수
	static int dupComCount; // 중복 조합 갯수
	static int num; // 뽑을 갯수
	
	public static void main(String[] args) {
		arr = new int[] {1,2,3,4};
		n = arr.length;
		num = 2;
		
		permutation(new ArrayList<Integer>(), num);
		System.out.println("[순열 갯수] " + perCount);
		System.out.println("-------------------");
		
		dupPermutation(new ArrayList<Integer>(), num);
		System.out.println("[중복순열 갯수] " + dupPerCount);
		System.out.println("-------------------");
		
		combination(new ArrayList<Integer>(), 0, num);
		System.out.println("[조합 갯수] " + comCount);
		System.out.println("-------------------");
		
		dupCombination(new ArrayList<Integer>(), 0, num);
		System.out.println("[중복조합 갯수] " + dupComCount);
	}
	
	// 순열
	public static void permutation(ArrayList<Integer> list, int count) {
		// 다 뽑았을 때
		if (count == 0) {
			System.out.println(list);
			perCount++;
			return;
		}
		
		for(int i = 0; i < n; i++) {
			if(list.contains(arr[i])) {
				continue;
			}
			list.add(arr[i]);
			permutation(list, count - 1); // 뽑을 때 마다 count - 1
			list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
		}
	}
	
	// 중복순열
	public static void dupPermutation(ArrayList<Integer> list, int count) {
		// 다 뽑았을 때
		if (count == 0) {
			System.out.println(list);
			dupPerCount++;
			return;
		}
		
		for(int i = 0; i < n; i++) {
			list.add(arr[i]);
			dupPermutation(list, count - 1); // 뽑을 때 마다 count - 1
			list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
		}
	}
	
	// 조합
	public static void combination(ArrayList<Integer> list, int index, int count) {
		// 다 뽑았을 때
		if (count == 0) {
			System.out.println(list);
			comCount++;
			return;
		}
		
		for(int i = index; i < n; i++) {
			list.add(arr[i]);
			combination(list, i + 1,count - 1); // 뽑을 때 마다 count - 1
			list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
		}
	}
	
	// 중복조합
	public static void dupCombination(ArrayList<Integer> list, int index, int count) {
		// 다 뽑았을 때
		if (count == 0) {
			System.out.println(list);
			dupComCount++;
			return;
		}
		
		for(int i = index; i < n; i++) {
			list.add(arr[i]);
			dupCombination(list, i,count - 1); // 뽑을 때 마다 count - 1
			list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 
		}
	}
}