[알고리즘] 순열, 중복 순열, 조합, 중복 조합 - 자바

1. 순열(Permutation)

---

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현할 수 있다. 

수식으로 나타내면 다음과 같다.

위 식을 간략화 하면 다음과 같다

 

순열 만드는 방법으로 반복문과 재귀문을 활용한 방법이 있다.

먼저 반복문으로 순열을 구하는 방법은 다음과 같다.

1. 기존 수와 중복되지 않게 숫자를 한 개씩 뽑는 일을 가능한 모든 수에 대해 반복해서 시도한다.
2. 목표하는 횟수만큼 "1"을 반복

(뽑는 횟수가 고정되어 있다면 목표하는 횟수까지 돌아가는 반복문으로 해결할 수 있지만, 정해지지 않았다면 뽑는 횟수만큼 재귀적으로 호출하는 구조를 이용하는 것이 적합할 수 있다.) (여기를 참고)

 

아래 코드는 반복문을 이용해 배열의 원소를 swap하여 순열을 구하는 방법이다.

public class PermutationRecursive { 
    public static void main(String[] args) { 
        String str = "ABC"; 
        int n = str.length(); 
        Permutation permutation = 
        new Permutation(); 
        permutation.permute(str, 0, n-1); 
    } 
    
    private void permute(String str, int l, int r) { 
        if (l == r) System.out.println(str); 
        else { 
            for (int i = l; i <= r; i++) { 
                str = swap(str,l,i); 
                permute(str, l+1, r); 
                str = swap(str,l,i); 
            } 
        } 
    } 

    public String swap(String a, int i, int j) { 
        char temp; 
        char[] charArray = a.toCharArray(); 
        temp = charArray[i] ; 
        charArray[i] = charArray[j]; 
        charArray[j] = temp; 
        
        return String.valueOf(charArray); 
    } 
}

출력

ABC
ACB
BAC
BCA
CBA
CAB

 

1-1. 순열 구현

재귀문으로 순열을 구현하는 방법은 다음과 같다.

1. 기존 수와 중복되지 않게 숫자를 한 개씩 뽑는 일을 가능한 모든 수에 대해 반복해서 시도
2. 현재까지 뽑은 순열 수(다음 수가 들어갈 index)를 넘겨주며 재귀 호출
3. 중복 검사 조건을 적절하게 초기화
   1. 인덱스에 해당하는 숫자가 사용중인지 저장하는 boolean 배열을 생성
   2. 해당 인덱스 값을 참조했을 때 true면 이미 사용 중이므로 다음 인덱스로 넘어가서 진행

 

package day0804.practice;

import java.util.Arrays;
import java.util.Scanner;

public class Permutation {
    static int n, r, totalCnt;    // 전역변수 n(숫자 전체 개수), r(택하는 수), 카운트 갯수 선언
    static int[] nums;            // 뽑은 숫자들을 저장할 배열 
    static int[] inputArr;        // 전체 숫자가 저장된 배열
    static boolean[] isSelect;    // 뽑현던 숫자를 다시 뽑지 않게 하기 위한 숫자 체크
    public static void main(String[] args) {
    	System.out.println("n과 r을 입력하세요 (ex=>4 2)");
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        totalCnt = 0;
        
        nums = new int[r];  // 택하는 숫자만큼 배열 생성 (뽑은 숫자를 저장할 배열)
        isSelect = new boolean[n+1]; // 숫자체크 배열 생성
        inputArr = new int[n]; // 사용자가 입력하여 저장할 수 배열
        
        // 전체 숫자가 저장된 배열에 값 입력
        for(int i = 0; i < n; i++) {
        	inputArr[i] = sc.nextInt();
        }
        
        permutation(0);
        System.out.println("순열의 총 경우의 수 = " + totalCnt);
    }
    
    
    public static void permutation(int cnt) {
    	// 카운트 숫자를 매개변수로 주어 뽑으려는 수까지 cnt를 세게되면 메서드 종료
    	if(cnt == r) {
    		totalCnt++;
    		System.out.println(Arrays.toString(nums));
    		return;
    	}
    	
    	for (int i = 0; i < n; i++) {
    		// 시도하는 수가 선택되었는지 판단한다. 
			if(isSelect[i]) continue;
			// 체크되어 있지 않았다면(선택되지않은 수) 뽑으려는 배열에 값 저장
			nums[cnt] = inputArr[i];
			isSelect[i] = true; // 숫자를 뽑았다면 true (체크됨)
			permutation(cnt+1); // 다음 숫자 뽑으러 가기
			isSelect[i] = false; // 사용한 수를 다시 되돌림
		}
    }
}

이를 입력과 출력을 수행하면 다음과 같다.

// 입력
n과 r을 입력하세요 (ex=>4 2)
5 3
2 4 6 8 10
// 출력
순열의 총 경우의 수 = 60

 

1-2. 중복 순열 구현

중복순열은 순열과 다르게 다음 수를 선택할때 중복 선택을 허용한다. 

중복순열의 경우의 수는 다음과 같다.

위의 중복 순열의 경우의 수를 일반화하면, n개의 수 중 r개를 선택하는 중복 순열은 n의 r승개의 경우의 수를 가짐을 알 수 있다.

 

위의 순열과 다른점은 isSelected로 중복을 체크하는 부분의 유무이다. 

package day0804.practice;

import java.util.Arrays;
import java.util.Scanner;

public class Permutation {
    static int n, r, totalCnt;    // 전역변수 n(숫자 전체 개수), r(택하는 수), 카운트 갯수 선언
    static int[] nums;            // 뽑은 숫자들을 저장할 배열 
    static int[] inputArr;        // 전체 숫자가 저장된 배열
    public static void main(String[] args) {
    	System.out.println("n과 r을 입력하세요 (ex=>4 2)");
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        totalCnt = 0;
        
        nums = new int[r];  // 택하는 숫자만큼 배열 생성 (뽑은 숫자를 저장할 배열)

        inputArr = new int[n]; // 사용자가 입력하여 저장할 수 배열
        
        // 전체 숫자가 저장된 배열에 값 입력
        for(int i = 0; i < n; i++) {
        	inputArr[i] = sc.nextInt();
        }
        
        permutation(0);
        System.out.println("순열의 총 경우의 수 = " + totalCnt);
    }
    
    
    public static void permutation(int cnt) {
    	// 카운트 숫자를 매개변수로 주어 뽑으려는 수까지 cnt를 세게되면 메서드 종료
    	if(cnt == r) {
    		totalCnt++;
    		System.out.println(Arrays.toString(nums));
    		return;
    	}
    	
    	for (int i = 0; i < n; i++) {
			nums[cnt] = inputArr[i];
			permutation(cnt+1); // 다음 숫자 뽑으러 가기
		}
    }
}

 

2. 조합(Combination)

---

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(Combintaion)이라고 부른다. 

순열과 다르게 순서를 고려하지 않기 때문에 조합의 경우의 수 =  순열의 경우의 수 / r! (r팩토리얼) 이다.

 

2-1. 조합

조합을 수식으로 나타내면 다음과 같다. 

 

백트래킹을 이용하여  조합구현하면 다음과 같다. 

import java.util.Arrays;
import java.util.Scanner;

public class CombinationTest {
	static int N, R, totalCnt;
	static int[] nums, input; // 뽑힌 숫자들과, 전체 숫자 리스트 선언

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("N입력 : ");
		N = sc.nextInt();
		System.out.print("R입력 : ");
		R = sc.nextInt();
        
		totalCnt = 0; // 경우의 수 카운트

		nums = new int[R]; // 뽑은 숫자 리스트 
		input = new int[N]; // 전체 숫자 리스트 입력
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt(); 
		}
		
		combination(0,0);
		System.out.println("총 경우의 수 : " + totalCnt);
		
	}

	// cnt: 카운트직전까지 뽑은 조합에 포함된 수의 갯수
    // start: 탐색을 시작할 인덱스 위치
	public static void combination(int cnt, int start) {
		
        // 기저조건 만족 : 뽑아야 할 숫자 개수를 만족했을 때
		if(cnt == R) {
			totalCnt++;
			System.out.println(Arrays.toString(nums));
			return;
		}
		
		// 가능한 모든 수에 대해 시도 (input배열의 모든 수 시도)
		// start부터 처리시 중복 수 추출 방지 및 순서가 다른 조합 추출 방지	
		for(int i = start; i < N; i++) {
			// start위치부터 처리됐으므로 수열과 다르게 중복체크할 필요가 없다. 
			// 앞쪽에서 선택되지 않았다면 수를 사용
			nums[cnt] = input[i];
			// 다음 수 뽑으러 가기
			combination(cnt+1, i+1);
		}
	}
}

출력

N입력 : 5
R입력 : 3
1 2 3 4 5
총 경우의 수 : 10

 

2-2. 중복 조합 

중복조합은 중복을 허용하는 조합이다.

중복조합의 수식은 다음과 같다. 

위의 조합 코드에서 새로운 수를 뽑을 때 매개변수로 i+1을 해주었는데 중복이 나오지 않게 탐색하려고 하였다.

하지만 중복조합은 중복을 허용하므로 매개변수 i를 주어 같은수를 뽑을 수 있게 하였다. 

 

구현은 다음과 같다.

import java.util.Arrays;
import java.util.Scanner;

public class CombinationDuplicate {
	static int N, R, totalCnt;
	static int[] nums, input; // 뽑힌 숫자들과, 전체 숫자 리스트 선언

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("N입력 : ");
		N = sc.nextInt();
		System.out.print("R입력 : ");
		R = sc.nextInt();
        
		totalCnt = 0; // 경우의 수 카운트

		nums = new int[R]; // 뽑은 숫자 리스트 
		input = new int[N]; // 전체 숫자 리스트 입력
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt(); 
		}
		
		combination(0,0);
		System.out.println("총 경우의 수 : " + totalCnt);
	}

	// cnt: 카운트직전까지 뽑은 조합에 포함된 수의 갯수
    // start: 탐색을 시작할 인덱스 위치
	public static void combination(int cnt, int start) {
		
        // 기저조건 만족 : 뽑아야 할 숫자 개수를 만족했을 때
		if(cnt == R) {
			totalCnt++;
			System.out.println(Arrays.toString(nums));
			return;
		}
		
		// 가능한 모든 수에 대해 시도 (input배열의 모든 수 시도)
		// start부터 처리시 중복 수 추출 방지 및 순서가 다른 조합 추출 방지	
		for(int i = start; i < N; i++) {
			// start위치부터 처리됐으므로 수열과 다르게 중복체크할 필요가 없다. 
			// 앞쪽에서 선택되지 않았다면 수를 사용
			nums[cnt] = input[i];
			// 다음 수 뽑으러 가기
			combination(cnt+1, i);
		}
	}
}

 

출력

N입력 : 5
R입력 : 3
총 경우의 수 : 35