순열,중복순열/조합,중복조합 구현

순열(Permutation)

---

• 요소 n개 중 r개를 뽑아 정렬하는 경우의 수로 요소의 순서를 구분한다.
  • e.g. [1,2]와 [2,1] 은 순서가 다르기 때문에 다른 경우의 수로 판단

순열 경우의 수 공식

구현

 

pubilc class Solution{
	public static void permutation(int arr[],int[] out,boolean[] visited,int depth,int r){
    	if(depth==r){
        	for(int num:out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i =0; i<arr.length; i++){
        	if(!visited[i]){
            	visited[i]=true;
                out[depth] = arr[i];
                permutation(arr,out,visited,depth+1;r);
                visitied[i] = false;
            }
        }
    }
    public static void main(String[] args){
    	 int[] arr = {1,2,3};
         int r = 2;
         permutation(arr,new int[r], new boolean[arr.length],0,r);
    }
}

 

 

중복 순열

---

• 요소 n개 중 r개를 뽑아 정렬하는 경우의 수로 요소의 순서를 구분하며 요소의 중복이 가능하다.

구현

pubilc class Solution{
	public static void permutation(int arr[],int[] out,boolean[] visited,int depth,int r){
    	if(depth==r){
        	for(int num:out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i =0; i<arr.length; i++){
            out[depth] = arr[i];
            permutation(arr,out,depth+1,r);
        }
    }
    public static void main(String[] args){
    	 int[] arr = {1,2,3};
         int r = 2;
         permutation(arr,new int[r], new boolean[arr.length],0,r);
    }
}

 

 

조합(Combination)

---

• 요소 n개 중 r개를 뽑아 정렬하는 경우의 수로 요소의 순서를 구분하지 않는다.

조합 경우의 수 공식

구현

pubilc class Solution{
	public static void combination(int arr[],boolean[] visited,int start,int depth,int r){
        if(depth==r){
            for (int i = 0; i < arr.length; i++) {
                if(visited[i]) System.out.println(arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i =start; i<arr.length; i++){
            if(!visited[i]){
                visited[i]= true;
                combination(arr,visited,i+1,depth+1,r);	//현재 선택한 원소보다 뒤에 있는 원소에 대해서만 탐색할 수 있도록 i+1
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args){
        int[] arr = {1,2,3};
        int r = 2;
        combination(arr,new boolean[arr.length],0,0,r);
    }
}

• 조합의 경우 [1,2]와 [2,1]가 같다고 보기 때문에 [1,2]만을 카운트 할 수 있도록 현재 선택한 원소보다 뒤에 있는 원소에 대해서만 탐색을 진행한다.

 

중복 조합

---

• 요소 n개 중 r개를 뽑아 정렬하는 경우의 수로 요소의 순서를 구분하지 않으며 요소의 중복이 가능하다.

구현

pubilc class Solution{
	public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int num : out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            out[depth] = arr[i];
            combination(arr, out, i, depth+1, r);	//현재 선택한 요소 포함할 수 있도록 i만 넘겨줌
        }
    }
    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new int[r], 0, 0, r);
    }
}