[ 기초수학| JAVA ] - 순열 & 조합 < Permutation / Combination >

 

순열과 조합 

< Permutation / Combination >

 

 

 

1) 순열

 [ Permutation ]

 

-  서로 다른 n개 중에 r개를 선택하는 경우의 수

(순서가 존재O, 중복허용X)

 

- Determines the number of possible arrangements in a set when the order of the arrangements matters.

 

- 순열 규칙 

(1) 대상: 서로 다른 n개

(2) 갯수 : r개

(3) 중복 : X 

(4) 순서의 구분 : O 

 

 

 

 

import java.util.stream.IntStream;

System.out.println(" [ Factorial ] :");

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

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

// IntStream 사용
System.out.println(IntStream.range(2,6).reduce(1,(x,y) -> (x * y))); // 2,3,4,5

System.out.println(" [ Permutation ] ");

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

for(int i = n; i >= n-r +1; i --){
	result *=1;
    fe
	

}

// 1,2,3,4를 이용하여 세자리 자연수를 만드는 방법 - 1
// n = 4, r = 3
 
public class Practice1{
	void permutation(int[] arr, int depth, int n, int r){
    
    	// depth == 3
    	if(depth == r){
        	for(int i = 0; i < r; i ++){
            	System.out.println(arr[i] + " ");
            }
        	System.out.println();
            return;
        }
    
    	for(int i = depth; i < n; i++){
        	swap(arr,depth,i);
        	permutation(arr, depth +1, n, r);
        	swap(arr,depth,i); 
        }

    }

	void swap(int[] arr, int depth, int idx){
    	int tmp = arr[deptt];
        arr[depth] = arr[idx];
        arr[idx] = tmp;
     
    }
}

// 1,2,3,4를 이용하여 세자리 자연수를 만드는 방법 - 2
// n = 4, r = 3
 
public class Practice1{
	void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] opt){
  	
    	if(depth == r){
    		System.out.println(Arrays.toString(out));
       	 	return;
   		 }
    
    	for(int i = 0; i < n; i++){
    		if(visited[i] != true){
        		visited[t] = true;
            	out[depth] = arr[i];
            	permutation(arr, depth+1, n,r, visited, out);
            	visited[i] = false;
       	 	}
   		 }
 	}   
    
 	public static void main(String[] args){
    
    // test code
    int n = 4;
    int r = 3;
    int [] arr = {1,2,3,4};
    boolean[] visited = new boolean[n];
    int[] out = new int[r];
    
    Practice2 p = new Practice2();
    p.permutation(arr,0,n,r,visited,out);
    
    
    
    
    
    }   
    
    
    
    
    
    
}

 

 

 

 

 

 

 

 

 

 

2) 조합

[ Combination ]

 

 

-  서로 다른 n개 중에 r개를 선택하는 경우의 수

(순서가 존재 X, 중복허용 X)

 

 

- a combination is a selection of items from a set that has distinct members, such that

the order of selection does not matter

 

 

- 조합 규칙 

(1) 대상: 서로 다른 n개

(2) 갯수 : r개

(3) 중복 : X 

(4) 순서의 구분 : X

 

 

System.out.println(" [ Combination ] ");

int n = 4;
int r = 2;

int nResult = 1;
for(int i = n; i >=n - r +1; i--){
	pResult *= i;
}

int rResult = 1;
for(int i = 1; i <=r; i++){
	rResult *= i;
}
Systen.out.println(" Result : " + pResult / rResult);

 // 1,2,3,4를 이용하여 세 자리 자연수를 만드는 방법
 
 public class Practice{
 	void combination(int[] arr, boolean[] visited, int depth, int n, int r){
    	
        if(r == 0)
        {
        	for(int i = 0; i < n; i++){
            	if(visited[i]){
                	System.out.println(arr[i] + " ");
                }
            }
        	System.out.println();
            return;
        }
        
        if(depth == n){
        	return;
        }
        
    	visited[depth] = true;
        combination(arr,visited, depth+1,n,r-1);
        
        visited[depth] = false;
        combination(arr,visited, depth+1,n,r);
    
    
    
    
    
    }
 
 
 	public static void main(Strin[] args){
    // test code
    int[] arr = {1,2,3,4};
    boolean[] visited = {false, false, false, false};
    
    Practice p = new Practice();
    p.combination(arr, visited, 0,4,3);
  
    }
 
 
 
 
 
 
 
 }