n개의 원소 중 m개를 고르는 순열과 조합

1. 문제 설명

(1) N개의 정수들 중에 M개를 고르는 (중복을 허용하는) 순열을 구하시요.

--> permDup() 메서드로 구현하여라.

 

(2) N개의 정수들 중에 M개를 고르는 (중복을 허용하지 않는) 순열을 구하시오.

--> permNotDup() 메서드로 구현하여라.

 

(3) N개의 정수들 중에 M개를 고르는 조합을 구하시오.

--> combi() 메서드로 구현하여라.

 

 

 

2. 풀이 및 코드

public class Main{
    static int N, M, ans;
    static int[] map;
 
    static boolean[] visited;
    
    static ArrayList<Integer> arr;
 
    public static void main(String[] args) throws Exception{
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(sc.readLine()); 
        N = Integer.parseInt(st.nextToken()); 
        M = Integer.parseInt(st.nextToken());
        solve();
    }
 
    public static void solve() {
        System.out.println("-----중복 있는 순열-----");
        map = new int[M];
        permDup(0);
 
        System.out.println("-----중복 없는 순열-----");
        map = new int[M];
        visited = new boolean[N+1];
        permNotDup(0);
        
        System.out.println("-----조합-----");
        arr = new ArrayList<>();
        combi(0);
    }
 
    public static void permDup(int depth) {
        if(depth==M) {
            for(int i=0; i<M; i++) {
                System.out.print(map[i]+" ");
            }
            System.out.println();
            return;
        }
 
        for(int i=1; i<=N; i++) {
            map[depth]=i;
            permDup(depth+1);
        }
    }
 
    public static void permNotDup(int depth) {
        if(depth==M) {
            for(int i=0; i<M; i++) {
                System.out.print(map[i]+" ");
            }
            System.out.println();
            return;
        }
 
        for(int i=1; i<=N; i++) {
            if(!visited[i]) {
                visited[i]=true;
                map[depth]=i;
                permNotDup(depth+1);
                visited[i]=false;
            }
        }
    }
 
    public static void combi(int depth) {
        if(depth==M) {
            for(int i=0; i<M; i++) {
                System.out.print(arr.get(i)+" ");
            }
            System.out.println();
            return;
        }
        
        int here = arr.isEmpty()?1:arr.get(arr.size()-1)+1;
        for(int i=here; i<=N; i++) {
            arr.add(i);
            combi(depth+1);
            arr.remove(arr.size()-1);
        }
    }
}