순열과 조합

백준의 N과 M으로 알아보는 순열과 조합 뽑기

순열

-모두 출력하는 순열 (동일 수 중복)

N과M 1

static class Permutation{
        int n;
        int r;
        int now[];
        ArrayList<ArrayList<Integer>> result;

        public Permutation(int n, int r){
            this.n = n;
            this.r = r;
            now = new int[r];
            result = new ArrayList<>();
        }

        public void perm(int[] arr, int depth){
            if(depth == r){
                for(int i = 0; i < now.length; i++){
                    System.out.print(now[i] + " ");
                }
                System.out.println();
                return;
            }
            for(int i = 0; i < n; i++){ //방문 처리 없이 모두 처리한다.
                now[depth] = arr[i];
                perm(arr, depth+1);
            }
        }
    }

-모두 출력하는 순열 (동일 수 배제)

N과M 3

static class Permutation{
        int n;
        int r;
        int now[];
        ArrayList<ArrayList<Integer>> result;

        public Permutation(int n, int r){
            this.n = n;
            this.r = r;
            now = new int[r];
            result = new ArrayList<>();
        }

        public void perm(int[] arr, int depth){
            if(depth == r){
                for(int i = 0; i < now.length; i++){
                    System.out.print(now[i] + " ");
                }
                System.out.println();
                return;
            }
            for(int i = 0; i < n; i++){ //방문 처리 없이 모두 처리한다.
                 if(visited[i]) continue;
                 output[depth] = arr.get(i);
                 visited[i] = true;
                 dfs(depth+1);
                 visited[i] = false;
            }
        }
    }

     //변수
    static boolean visited[];
    static ArrayList<Integer> arr = new ArrayList<>();
    static int n,r;

   public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        visited = new boolean[n];

        for(int i = 1; i <=n; i++){
            arr.add(i);
        }
       Permutation p = new Permutation(n, r);
       p.perm(arr.stream().mapToInt(Integer::intValue).toArray(), 0);
       // Combination comb = new Combination(n, r);
        //comb.comb(arr, 0, 0, 0);

    }
}

-idx로 진행하는 수열(중복수 허용)

N과M 4

import java.util.*;

public class Main {

    static class Permutation{
        int n;
        int r;
        int now[];
        ArrayList<ArrayList<Integer>> result;
        public Permutation(int n, int r){
            this.n = n;
            this.r = r;
            now = new int[r];
            result = new ArrayList<>();
        }

        public void perm(int[] arr, int idx, int depth){
            if(depth == r){
                for(int i = 0; i < now.length; i++){
                    System.out.print(now[i] + " ");
                }
                System.out.println();
                return;
            }
            for(int i = idx; i < n; i++){
                now[depth] = arr[i];
                perm(arr,i, depth+1);
            }
        }
    }
    static boolean visited[];
    static ArrayList<Integer> arr = new ArrayList<>();
    static int n,r;
   public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        visited = new boolean[n];

        for(int i = 1; i <=n; i++){
            arr.add(i);
        }
       Permutation p = new Permutation(n, r);
       p.perm(arr.stream().mapToInt(Integer::intValue).toArray(),0, 0);
    }
}

---

조합

-기본 조합

N과M 2

    static class Combination{
        int n;
        int r;
        int[] now;
        ArrayList<ArrayList<Integer>> result;

        public Combination(int n, int r){
            this.n = n;
            this.r = r;
            now = new int[r];
            result = new ArrayList<>();
        }

        public void comb(ArrayList<Integer> arr, int depth, int target, int idx){
            if(depth == r){
                ArrayList<Integer> temp = new ArrayList<>();
                for(int i = 0; i < now.length; i++){
                    System.out.print(arr.get(now[i]) + " ");
                }
                System.out.println();
                return;
            }
            if(target == n) return;
            now[idx] = target;
            comb(arr,depth+1,target+1,idx+1);
            comb(arr,depth,target+1,idx);
        }
    }

   public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();

        Combination comb = new Combination(n, r);
        comb.comb(arr, 0, 0, 0);

    }
}