자바 순열과조합

순열

서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현합니다.

nPr

 

A B C 중 2개를 뽑는다고 한다면 결과는 아래와 같습니다.

A, B

A, C

B, A

B, C

C, A

C, B

 

순열은 이처럼 AB와 BA // AC와 CA // BC와 CA를 다른 경우의 수로 봅니다.

만약 AB = BA가 성립한다면 순서가 의미 없기 때문에 이는 순열이 아니라 조합으로 접근해야 합니다.

 

프로그래밍적으로 접근해보자면

A를 뽑는다면 A는 더 이상 뽑지 못하고 다음 후보로는 (B, C)가 올 수 있습니다.

만약 다음 후보에 B, C 어떤 것이 뽑히던 2개를 뽑았기 때문에 끝나게 됩니다.

 

따라서 처음에 올 수 있는 후보는 3가지 (A, B, C)

그다음 올 수 있는 후보는 처음에 뽑힌 후보를 제외한 2가지가 됩니다.

B가 뽑혔다고 가정하면 : A, C (2개를 순차적으로 뽑고 끝나게 됩니다)

경우의 수 : 3 x 2

 

순열 nPr의 경우의 수는 n * n-1 * n-2... * (n-r+1)입니다.

따라서 12P12만 되더라도 4억 7천만의 경우의 수가 나오기 때문에 알고리즘 문제에서 순열로 접근해야 하지만 n의 범위가 11을 넘어가게 된다면 다른 효율적인 방법을 고려해보아야 합니다.

 

{1, 2, 3}을 포함하는 모든 순열을 생성하고자 합니다.

이때 반복문을 통해 순열을 생성해 보겠습니다.

for(int i=1; i<=3; i++){
	for(int j=1; j<=3; j++){
		if(j==i){
    		continue;
		}
		for(int k=1; k<=3; k++){
			if( k!= i && k!=j){
				System.out.println(i + " " + j + " " + k);
			}
		}
	}
}

만약 1,2,3이 아닌 1, 2, 3, 4, 5를 생성해야 한다면 코드의 가로길이가 엄청나게 길어지기 때문에 가독성이 너무 떨어집니다.

또한 조건을 계속 추가해야 하기 때문에 경우에 따라 다른 순열이 필요한 경우에는 절대로 반복문을 통해서 해결할 수 없습니다. ( nPr에서 r이 계속 달라지는 경우 반복문 사용 불가 : r의 개수 =  반복문의 중첩의 개수)

 

이제 재귀를 통해 순열을 생성해 보겠습니다.

재귀에서의 반복은 stack이 하나 쌓일 때입니다.

따라서 처음 stack을 쌓을 때는 3가지의 경우의 수를 넣어주어야 합니다. (1, 2, 3중 하나)

그다음 stack을 쌓을 때는 2가지 경우의 수를 넣어주어야 합니다.

 

다음은 가장 보편적이며 이해하기 쉬운 방법입니다.

public class Permutation {
	static int arr[] = {1, 2, 3};
	static int length = arr.length;
	static int num[] = new int[length];
    
	public static void main(String[] args) {    
        boolean isSelected[] = new boolean[arr.length];
        doPermutation(0);
	}
    
	static void doPermutation(int cnt){
		if(cnt == length){
			//순열 생성 완료
			return;
		}
    	
		for(int i=0; i<length; i++){
			if(isSelected[i]){
				continue;
			}
			num[cnt] = arr[i];
			isSelected[i] = true;
			doPermutation(cnt+1);
			isSelected[i] = false;
		}        
	}
}

isSelected라는 boolean 배열을 사용합니다.

처음 stack이 쌓일 때는 num [0]에 arr [0~2] 1,2,3이 쌓이게 됩니다.

다음 stack이 쌓일 때는 num [1]에 arr [0~2] 첫 번째 수를 제외한 2개의 수가 쌓이게 됩니다.

이것을 반복합니다.

매번 전체 배열을 탐색해야 합니다. ( 0~ n-1까지)

 

 

조금 더 효율적인 순열 방법에 대해 알아보겠습니다.

public class Permutation {

	public static void main(String[] args) {
		Permutation ex = new Permutation();
		int[] arr = {1, 2, 3, 4};
		// arr 배열 자체를 메소드에서 정렬한다.
		ex.doPermutation(arr, 0);

	}

	public void doPermutation(int[] arr, int startIdx) {
		int length = arr.length;
		if(startIdx == length - 1) {
			for(int n: arr)
				System.out.print(n + " ");
			System.out.println();
			return;
		}
		
		for(int i = startIdx; i < length; i++) {
			swap(arr, startIdx, i);
			doPermutation(arr, startIdx + 1);
			swap(arr, startIdx, i);
		}
	}
	
	public void swap(int[] arr, int n1, int n2) {
		int temp = arr[n1];
		arr[n1] = arr[n2];
		arr[n2] = temp;
	}
}

다음은 swap이라는 방식을 사용한 순열 방법입니다.

swap(i, j)는 말 그대로 i인덱스와 j인덱스의 원소를 교환합니다.

 

재귀에서의 반복은 stack이 하나 쌓일 때입니다.
따라서 처음 stack을 쌓을 때는 3가지의 경우의 수를 넣어주어야 합니다. (1, 2, 3중 하나)
그다음 stack을 쌓을 때는 2가지 경우의 수를 넣어주어야 합니다.

위의 내용을 이해하셨다면 다음도 쉽게 이해하실 겁니다.

 

처음 stack에는 (startIdx = 0이므로) 0번째 index가 스택에 쌓입니다.

 

이때 0번째 인덱스와 (0~N-1) 번째 인덱스를 교환하게 되면 자연스럽게 첫 번째 stack에는 N가지의 경우의 수가 모두 들어갑니다.

 

그다음 stack에는 0번째 index를 제외한 (1~N-1) 번째 인덱스를 교환하게 되고 자연스럽게 두 번째 stack에는 처음 들어간 경우를 제외한 N-1가지의 경우의 수가 모두 들어가게 됩니다.

 

 

isSelected는 매번 전체 배열을 탐색해야 한다면 swap()을 사용하면 n번 , n-1번,.... 1번 이런 식으로 스택이 쌓일 때마다 탐색하는 수가 줄어들게 됩니다.

 

 

 

조합

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

서로 다른 n개 중 r개를 택하는 조합은 아래와 같이 표현합니다.

nCr

A B C 중 2개를 뽑는다고 한다면 결과는 아래와 같습니다.

A, B

A, C

B, C

 

순열과는 다르게 AB = BA를 동일하게 보지 않습니다.

만약 AB!= BA가 성립한다면 순서가 의미 있기 때문에 이는 조합이 아니라 순열로 접근해야 합니다.

 

프로그래밍적으로 접근해보자면

A를 뽑는다면 A는 더 이상 뽑지 못하고 다음 후보로는 (B, C)가 올 수 있습니다.

만약 다음 후보에 B, C 어떤 것이 뽑히던 2개를 뽑았기 때문에 끝나게 됩니다.

 

따라서 처음에 올 수 있는 후보는 3가지 (A, B, C)

그다음 올 수 있는 후보는 처음에 뽑힌 후보를 제외한 2가지가 됩니다.

B가 뽑는다고 가정하면 : A, C ( 둘 중 하나를 뽑게 되면 끝나게 됩니다)

경우의 수 : 3 x 1

 

{1, 2, 3, 4}중 원소 3개를 포함하는 조합을 생성하고자 합니다.

이때 반복문을 통해 조합을 생성해 보겠습니다.

for(int i=1; i<=4;){
	for(int j=i+1; j<=4; j++){
		for(int k=j+1; k<=4; k++){
			System.out.println(i + " " + j + " " + k);
		}
	}
}

 

순열과 마찬가지로 경우에 따라 다른 조합이 필요한 경우에는 절대로 반복문을 통해서 해결할 수 없습니다. ( nCr에서 r이 계속 달라지는 경우 반복문 사용 불가 : r의 개수 =  반복문의 충접의 개수)

 

이제 재귀를 통해 조합을 생성해 보겠습니다.

public class Combination {
	static int[] arr = {1, 2, 3, 4};
	static int[] number = new int[arr.length];
    
	public static void main(String[] args) {				
		doCombination(0,0);
	}

	static void doCombination(int cnt, int start) {
		if(cnt ==3){
			//3개의 조합 생성
			System.out.println(Arrays.toString(numbers));
			return;
		}
		//start 매개변수를 통하여 중복이 일어나지 않게 함.
		for(int i=start; i<arr.length; i++){
			number[cnt] = arr[i];
			doCombinatioin(cnt+1, i+1); //다음자리는 현재 뽑은 i의 다음수부터 시작하도록 전달
		}                
	}
}

순열에서 하는 visited를 사용하지 않기 때문에 더 간결하고 이해하기 쉽습니다.

처음 stack에는 (cnt= 0이므로) number배열의 0번째 index에 1~4까지의 수가 스택에 쌓입니다.

 

그다음 stack에는 number배열의 0번째 index에 들어간 수를 제외한 수가 number배열의 1번째 index에 쌓이게 됩니다.

 

 

 

 

 

https://swycha.tistory.com/133

[알고리즘] 순열과 조합 (java)