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

순열 (Permutaion)

Permutaion의 앞글자를 따서 P로 나타냄.

nPr의 의미는 n개의 숫자에서 r개를 뽑아 정렬하는 가짓수이다. 

예를 들어 {1, 2, 3}이란 수열이 있고, 여기서 두개를 뽑아 정렬하고자 할 때,

n = 3, r = 2라고 하면, 가짓수는 3P2가 된다. 

 

가짓수를 출력해보면

{1, 2}, {2, 1}

{1, 3}, {3, 1}

{2, 3}, {3, 2}

순서도 고려하므로 {1, 2}와 {2, 1}은 다르게 취급한다. 

 

조합 (Combination)

Combination의 앞글자를 따서 C로 나타낸다. 

nCr의 의미는 n개의 숫자에서 r개를 뽑는 경우의 수이다. 

순서가 달라도 내용물이 같으면 같은 수열이다. 

예를 들어 {1, 2, 3}이란 수열이 있고, 여기서 2개를 뽑는다고 할 때,

n = 3, r = 2이다. 경우의 수는 3C2가 된다. 

 

경우의 수를 출력하면

{1, 2}

{1, 3}

{2, 3}

위에서 구한 순열의 결과와 비교해보면

{1, 2}, {2, 1}이 같다고 취급된다. 순서가 상관없기 때문이다. 

 

[조합 구현하기 (nCr)]

public class Combination {

	public static void main(String[] args) {
		Combination ex = new Combination();
		int[] arr = {1, 3, 5, 7, 9};
		int n = arr.length;
		int r = 3;
		// 크기가 5인 수열 arr에서 r인 3r개를 뽑은 경우를 출력한다. 
		int[] combArr = new int[n]; // 뽑은 원소의 인덱스를 저장하는 배열 
		
		ex.doCombination(combArr, n, r, 0, 0, arr);

	}
	
	public void doCombination(int[] combArr, int n, int r, int index, int target, int[] arr) {
		if(r == 0) {
			// 다 뽑았을 때 
			for(int i=0; i<index; i++)
				System.out.print(arr[combArr[i]] + " ");
			System.out.println();
		} else if (target == n) 
			return;
			//r개를 다 못뽑았는데 arr의 모든 원소를 다 검사했을 때, 실패 -> 아무것도 안하고 끝난다. 
		else {
			combArr[index] = target;
			doCombination(combArr, n, r-1, index+1, target+1, arr); // (i) 원소를 뽑는 경우 
			doCombination(combArr, n, r, index, target+1, arr); // (ii) 원소를 안뽑는 경우 
		}
	}

}

 

 

[출력 결과]

1 3 5 

1 3 7 

1 3 9 

1 5 7 

1 5 9 

1 7 9 

3 5 7 

3 5 9 

3 7 9 

5 7 9 

[순열 구현하기 (nPn)]

nPr을 구현하기 전에 nPn을 구현해보자.

즉, r = n인 경우이고 수열 그 자체를 정렬한 모든 경우를 출력하는 것이다. 

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()을 통해  startIdx번째 자리의 수가 1일때, 2일때, 3일때, 4일때..를 조사한다.

startIdx번째 자리를 선택한 후, Recursive를 통해 startIdx + 1번째  자리를 선택하고

이게 반복되다 startIdx가 arr의 마지막 자리를 가리킬 때 끝이 난다. 

 

재귀함수 후에 다시 swap()으로 바꿔준 값을 원상복구해야한다. 

그래야 제대로 각 자리수가 1일때, 2일때, 3일때, 4일때를 모두 조사할 수 있다. 

 

[출력 결과]

1 4 2 3 

2 1 3 4 

2 1 4 3 

2 3 1 4 

2 3 4 1 

2 4 3 1 

2 4 1 3 

3 2 1 4 

3 2 4 1 

3 1 2 4 

3 1 4 2 

3 4 1 2 

3 4 2 1 

4 2 3 1 

4 2 1 3 

4 3 2 1 

4 3 1 2 

4 1 3 2 

4 1 2 3 

 

[순열 구현하기 (nPr)]

nPr은 nPn과 nCr의 코드를 합친 코드이다. 

nCr을 통해 n개 중에 r개를 뽑은 후, 

그 r개 수로 이루어진 수열을 doPermutation()으로 정렬해주면 된다. 

public class Permutation2 {

	public static void main(String[] args) {
		Permutation2 ex = new Permutation2();
		int[] arr = {1, 3, 5, 7, 9};
		
		int n = arr.length;
		int r = 3;
		int[] combArr = new int[r];
		ex.doCombination(combArr, arr, n, r, 0, 0);

	}
	public void doCombination(int[] combArr, int[] arr, int n, int r, int index, int target) {
		if(r == 0) {
			doPermutation(combArr, 0);
			System.out.println("------------------------");
		} else if(target == n)
			return;
		else {
			combArr[index] = arr[target];
			doCombination(combArr, arr, n, r-1, index+1, target+1);
			doCombination(combArr, arr, n, r, index, target+1);
		}
	}
	public void doPermutation(int[] arr, int startIdx) {
		int length = arr.length;
		if(startIdx == length - 1) {
			for(int item: arr)
				System.out.print(item + " ");
			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;
	}

}

 

[출력결과]

1 7 9 

1 9 7 

7 1 9 

7 9 1 

9 7 1 

9 1 7 

------------------------

3 5 7 

3 7 5 

5 3 7 

5 7 3 

7 5 3 

7 3 5 

------------------------

3 5 9 

3 9 5 

5 3 9 

5 9 3 

9 5 3 

9 3 5 

------------------------

3 7 9 

3 9 7 

7 3 9 

7 9 3 

9 7 3 

9 3 7 

------------------------

5 7 9 

5 9 7 

7 5 9 

7 9 5 

9 7 5 

9 5 7 

------------------------

 

 

[참고 및 코드 인용]

https://onsil-thegreenhouse.github.io/programming/algorithm/2018/04/05/permutation_combination/

[Algorithm] 수열의 순열과 조합 출력하기(nPr, nCr) - Onsil's blog