JAVA로 순열(Permuation) 구현하기

반응형

우리가 등학교 때 배웠던 '순열 & 조합' 기억할 것이다.

(아마 '확률과 통계' 과목에 나왔던 것으로 기억하는데, 예전 문과는 '미적분과 통계 기본'이라는 과목으로 배웠을 것이다.)

 

nPr

이 모양을 보면 기억이 날 것이다.

nPr은 'n개 중 r개를 중복을 허용하지 않으면서 뽑는 모든 순서의 수'이다.

계산은 사실 간단하다.

nPr = n!/(n-r)!

이 공식으로 교과서에 나와있던 걸 어렴풋이라도 기억할 것이다.

 

이걸 코딩으로 구현한다고 생각해보자.

그저 nPr 값만 구현한다고 하면

int numOfPer(int n, int r){
	return factorial(n)/factorial(n-r);
}

int factorial(int n){
	if(n==1)
    	return 1;
	return n*factorial(n-1);
}

이런 아주 아주 아주 간단한 문제가 될 것이다.

 

하지만 만약 단순히 값만 나타내지 말고 모든 경우의 수를 각각 보여달라고 하면 어떨까?

예를 들어서, 

 String[] arr = {"a", "b", "c", "d"};

이런 배열이 있고 중복을 허용하지 않으면서 2개를 고르는 모든 순서를 나열하라고 하는 것이다.

 

이러면 이야기가 좀 달라진다.

단순히 숫자로 보여주는 것이 아닌 모든 예시를 보여줘야 하기 때문에 좀 더 디테일하게 짜야한다.

 

728x90

 

우선, 사고의 순서를 정리해보자.

(1) 내가 채워야하는 만큼의 공백을 준비해두고

(2) 앞에서부터 그 공백을 하나씩 채워 나가면 될 것이다.

(3) 그 과정에서 사용한 것을 또 사용할 수는 없기 때문에 사용을 했는지 안 했는지에 대한 체크가 필요하다.

(4) 맨 처음 만든 공백이 비어있다면 체크가 안 된 글자를 넣어야 하는데, 이 과정은 반복이기 때문에 하나의 함수로 재귀를 돌리면 될 것이다.

(5) 하지만 종료는 되어야 한다. 종료는 공백이 가득차면 종료를 시키면 된다.

 

이제 이걸 코드로 작성해보자

// (1) 공백을 준비해둔다
// output은 앞으로 채워나갈 결과값
// visited는 방문을 했는지 체크하는 boolean[]
private static void perm(String[] arr, String output, boolean[] visited, int depth, int r) {
	
	// (5) 종료 단계
	// depth와 r이 같다는 건 공백이 없다는 것을 의미하기 때문에 종료해야 함
	if(depth==r) {
		// 여기서는 단순히 print하지만 그 값으로 어떤 걸 해도 상관없음
		System.out.println(output);
		// 종료
		return;
	}
	
	// (2) 공백을 채워나가는 과정
	for(int i=0;i<arr.length;i++) {
		// (3) 만약 아직 방문하지 않았다면
		if(visited[i] != true) {
			// output에 arr[i]를 추가해서 재귀를 넘기면 된다
			String temp =output;
			temp+=arr[i];
			// 그리고 이제 방문을 했으니 visited[i]는 true
			visited[i] = true;
			// (4) 그 상태로 재귀
			perm(arr, temp, visited, depth+1, r);
			// 이제 다시 원래대로 돌리고 for loop를 돌리면 된다.
			visited[i] = false;
		}
	}
}