[완전탐색] 순열 구하기 (조합 이용 방법, 추가 공간 사용 방법)

코드

1) 조합을 구한 뒤에 그 조합으로 순열 구하는 방식 (nCr -> rPr)

 

import java.util.*;
 
public class Main {
    //조합을 구한 후 순열 구하는 방식 => 두 개의 함수 재귀를 이용
    static int[] comb;
    
    //nPr 구하는 순열 함수
    public static void permutation(int n, int r, int[] arr) {
        comb = new int[r];
        dfs_comb(n,r,0,0,arr);
    }
    //순열 구하는 함수 nPn
    public static void dfs_per(int n, int r, int depth, int[] arr) {
        if(depth == r) {
            for(int i=0;i<r;i++)
                System.out.print(arr[i]+" ");
            System.out.println();
        }
        else {
            for(int i=depth;i<n;i++) {
                swap(depth,i,arr);
                dfs_per(n,r,depth+1,arr);
                swap(depth,i,arr);
            }
        }
    }
    //조합 구하는 함수 nCr
    public static void dfs_comb(int n, int r, int st, int depth, int[] arr) {
        if(depth == r)
            dfs_per(r,r,0,comb);
        else {
            for(int i=st;i<n;i++) {
                comb[depth] = arr[i];
                dfs_comb(n,r,i+1,depth+1,arr);
            }
        }
    }
    //스왑 함수
    public static void swap(int idx1, int idx2, int[] arr) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
    
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        permutation(5,3,arr);//5P3 예시
    }
}

 

 

 

2) 방문 여부 확인 배열을 추가로 사용하는 방식 (nPr 바로 구하기)

 

import java.util.*;
 
public class Main {
    //추가 저장공간을 이용하여 nPr 구하는 방식
    static boolean[] visited;//주어진 수열의 각 요소 방문 여부 배열
    static int[] tmp_list;//임시 배열
    
    //배열 초기화 및 재귀 시작
    public static void permutation(int n, int r, int[] arr) {
        tmp_list = new int[r];
        visited = new boolean[n];
        dfs_per(n,r,0,arr);
    }
    //순열 재귀
    public static void dfs_per(int n, int r, int depth, int[] arr) {
        if(depth == r) {
            for(int i=0;i<r;i++)
                System.out.print(tmp_list[i]+" ");
            System.out.println();
        }
        else {
            for(int i=0;i<n;i++) {
                if(!visited[i]) {//방문 안한 요소에 한하여 배열 값 변경
                    tmp_list[depth] = arr[i];
                    visited[i] = true;
                    dfs_per(n,r,depth+1,arr);
                    visited[i] = false;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        permutation(5,3,arr);//5P3 예시
    }
}