자바(Java) 순열(Permutation)과 조합(Combination)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. 순열(Permutation)

- 서로 다른 N개의 원소에서 R개를 중복없이 골라 순서에 상관있게 나열하는 것

- nPr로 표현(N개에서 r개를 뽑는다.)

- 5P3  = 5*4*3

 

2. 조합(Combination)

- 서로 다른 N개의 원소에서 R개를 순서 없이 고르는 것

- nCr로 표현

import java.util.*;

public class Solution {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
         
         
        //순열
        LinkedList<Integer> Per = new LinkedList<Integer>(); 
        //크기만큼 선언하고, 방문했는지 안했는지 확인
        int[] Check = new int[n];
        
        Permutation(n,r,Per,Check);
         
        //중복순열
        LinkedList<Integer> rePer = new LinkedList<Integer>();
        Repermutation(n,r,Per);
         
        //조합
        int[] comArr = new int[r];
        Combination(comArr,n,r,0,0); 
    }
	
	//순열
    public static void Permutation(int n, int r, LinkedList<Integer> perArr, int[] Check) {
        if(perArr.size() == r){
        	for(int i=0;i<perArr.size();i++) System.out.print(i + " ");
            System.out.println();
            return;
        }
         
        for(int i=0; i<n; i++){
            if(Check[i] == 0){
                perArr.add(i);
                Check[i] = 1;
                Permutation(n, r, perArr, Check);
                Check[i] = 0;
                perArr.removeLast();
            }
        }
    }
    
  //중복순열
    public static void Repermutation(int n, int r, LinkedList<Integer> rePerArr) {
        if(rePerArr.size() == r){
        	for(int i=0;i<rePerArr.size();i++) System.out.print(i + " ");
            System.out.println();
            return;
        }
         
        for(int i=0; i<n; i++){  
            rePerArr.add(i);
            Repermutation(n,r,rePerArr);
            rePerArr.removeLast();
        }
    }
	
    //조합
    public static void Combination(int[] comArr, int n, int r, int index, int idx) {
        if(r==0){
        	for(int i=0;i<comArr.length;i++) System.out.print(i + " ");
            System.out.println();
            return;
        }
        
        if(idx==n) return;
         
        comArr[index] = idx;
        
        Combination(comArr,n,r-1,index+1,idx+1);
        Combination(comArr,n,r,index,idx+1);
    }
    
    
}