[Java] 순열(Permutation)

팩토리얼(Factorial)

• 1에서 n까지 모든 자연수의 곱(n!)

n! = n(n - 1)(n - 2)(n - 3) .... 1

// 5!
int n = 5;
int result = 1; 

for(int i = 1; i <= n; i++) {
	result *= i;
}
System.out.println(result);      //120 출력


//Stream 이용
System.out.println(IntStream.range(2, 6).reduce(1, (x, y) -> (x * y)));


//재귀함수 이용
public int factorial(int num) {
	if (num == 1) {
    	return 1;
	}
    return num * factorial(num - 1);
}

순열(Permutation)

• 순서를 정해서 나열
• 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서O, 중복X)
  • 예1) 5명을 3줄로 세우는 방법
  • 예2) 서로 다른 4명 중 반장, 부반장을 뽑는 방법

nPr = n! / (n - r)! = n(n - 1)(n - 2) .... (n - r + 1)

//5명을 3줄로 세우는 경우의 수
int n = 5;
int r = 3;
int result = 1;

for(int i = n; i >= n - r + 1; i--) {
	result *= i;
}
System.out.println(result);             //60 출력

중복 순열

• 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서O, 중복O)
  • 예1) 서로 다른 4개의 수 중 2개를 뽑는 방법(중복 허용)
  • 예2) 후보 2명, 유권자 3명일 때 기명 투표 방법

n π r = n의 r승

//서로 다른 4개의 수 중 2개를 뽑는 경우의 수 (중복 허용)
int n = 4;
int r = 2;
int result = 1;

for(int i = 0; i < r; i++) {
	result *= n;
}
System.out.println(result);            //16 출력


//Math함수 이용
System.out.println(Math.pow(n , r));   //16.0 출력

원 순열

• 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수
  • 예) 원 모양의 테이블에 3명을 앉히는 경우

n! / n = (n - 1)!

int n = 3;
int result = 1;

for(int i = 1; i < n; i++) {
	result *= i;
}
System.out.println(result);     //2 출력


//Stream 이용
System.out.println(IntStream.range(2, n).reduce(1, (x, y) -> (x * y)));

순열 Practice

//1, 2, 3, 4를 이용하여 세자리 자연수를 만드는 방법(순서O, 중복X)의 각 결과를 출력하는 함수를 구현하시오.

void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
	if(depth == r) {
    	System.out.println(Arrays.toString(out));
        return;
    }
    
    for(int i = 0; i < n; i++) {
    	if(!visited[i]) {
        	visited[i] = true;
            out[depth] = arr[i];
            permutation(arr, depth + 1, n, r, visited, out);
            visited[i] = false;
        }
    }
}