알고리즘 공부 - 순열, 조합

순열(Permutation)

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

	int n=5, r=3;
    int result=1;
    
    for(int i=n; i>=n-r+1; i--) {
    	result *= i; // 60
    }

중복 순열

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

	int n=4, r=2;
    int result=1;
    
    for(int i=0; i<r; i++) {
    	result *= i; // 16
    }

원 순열

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

	int n=3;
    int result=1;
    
    for(int i=1; i<n; i++) {
    	result *= i; // 2
    }

문제 예시
1,2,3,4를 이용하여 세자리 자연수를 만드는 방법의 각 결과를 출력하시오

	static void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
    	if(depth==r) {
        	// 123 ~ 432 출력
        	System.out.println(Array.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;
            }
        }
    }
    public static void main(String[] args) {
    	int n=4, r=3;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];
        int[] out = new int[r];
        
        permutation(arr, 0, n, r, visited, out);
    }

조합(Combination)

• 서로 다른 n개 중에서 r개를 선택하는 경우의 수(순서 X, 중복 X)
  • 예시) 서로 다른 4명 중 주번 2명 뽑는 방법
    

	int n=4, r=2;
    int result=0;
    
    int pResult=1;
    for(int i=n; i>=n-r+1; i--) {
    	pResult *= i;
    }
    
    int rResult=1;
    for(int i=1; i<=r; i++) {
    	rResult *= i;
    }
    
    result = pResult/rResult; // 6

중복 조합

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

	int n=2, r=3;
    int result=0;
    
    int pResult=1;
    for(int i=n+r-1; i>=n; i--) {
    	pResult *= i;
    }
    // 2
    int rResult=1;
    for(int i=1; i<=r; i++) {
    	rResult *= i;
    }
    
    result = pResult/rResult; // 4

문제 예시
1, 2, 3, 4를 이용하여 세자리 자연수를 만드는 방법의 각 결과를 출력하시오

	static void combination(int[] arr, int depth, int n, int r, boolean[] visited) {
    	if(r==0) {
        	for(int i=0; i<n; i++) {
            	if(visited[i]) {
                	// 123 124 134 234 출력
                	System.out.println(arr[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        
        if(depth==n) return;
        
        visited[depth] = true;
        combination(arr, depth+1, n, r-1, visited);
        
        visited[depth] false;
        combination(arr, depth+1, n, r, visited);
    }
    
    public static void main(String[] args) {
    	int n=4, r=3;
    	int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];
        
        combination(arr, 0, n, r, visited);
    }