순열(permutation) 구현

순열?

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것 

nPr  = n*(n-1)*(n-2)* …*(n-r+1)

ex) 1~10의 숫자 중에서 3개의 숫자를 중복없이 순서에 상관있게 선택하는 경우의수
10Ρ3 = 10 x 9 x 8 = > 720 가지

 

 

구현 방법

1. 숫자를 담을 nums[] 배열과 방문처리를 해줄 visited[] 배열을 생성한다.
2. perm(0) 함수를 타고 0 ~ N 까지 for문을 돌면서 방문한 적이 없다면 방문처리와 함께 nums[] 배열에 값을 넣어주고 perm(cnt+1) 재귀함수를 탄다.
3. 계속 반복하다가 cnt 가 R(3)이 되었을 때, 배열을 출력하고 return 한다.

 

 

p[] 배열 중 R(3)개 를 nums[] 배열에 순서에 상관 있게 뽑는 예제

import java.util.Arrays;

public class PermTest {

	static int p[] = {1,2,3,4,5,6};
	static int N = p.length;
	static int R;
	static int count;
	static int[] nums;
	static boolean[] visited;
	public static void main(String[] args) {
		R =3;
		nums = new int[R];
		visited = new boolean[N];
		perm(0);
		System.out.println(count);
	}
	static void perm(int cnt) {
		if(cnt == R) { //R개가 선택 되었을 때
			count++; //갯수 세주고
			System.out.println(Arrays.toString(nums)); //nums 배열 출력
			return;
		}
		for (int i = 0; i < N; i++) {
			if(visited[i]) continue; //이부분지우면 중복순열
			visited[i] = true;
			nums[cnt] = p[i];
			perm(cnt+1);
			nums[cnt] = 0;
			visited[i] = false;
		}
	}
}

 

출력

[1,2,3] ~ [6,5,4] 까지 120개의 배열이 출력되는 것을 볼 수 있다.

 

 

 

 

 

 

 

 => count 의 갯수 출력

 

 

+) visited 방문처리 없이 코드를 돌리게 된다면 중복 순열을 구현 할 수 있다.
위의 예제에서 중복순열의 개수는 6x6x6 = 216 가지이다.

 

 

순열, 조합, 부분집합 코드는 알고리즘 풀이에 있어서 쏠쏠하게 자주 쓰이기 때문에 꼭! 외워두는 것이 좋다 ~,~