ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘 정리] 순열, next_permutation 구현
    Development/Algorithm 2020. 4. 29. 01:39

     

     

    다룰 내용

    • 순열이란 무엇인가?
    • 순열 구현
    • next_permutation이란 무엇인가?
    • next_permutation 구현

     

    순열이란 무엇인가?

    순서 있게 수들을 나열하는 것으로, 원소의 순서가 의미있다면 순열입니다.

    서로 다른 N개의 수 중에 R개를 선택하여 나열(nPr)로 표현할 수 있고 

    경우의 수를 구하면 nPr = n * n - 1 * n - 2 ~~ n - r + 1 이렇게 구할 수 있습니다.

     

     

    순열을 구현하는 방법

    1. 각 자리에서 앞 쪽에 선택된 수를 배제합니다. (앞쪽에서 선택된 수를 알기 위해 boolean 배열 사용)
    2. 현재 자리에서 선택 가능한 수를 선택합니다.
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    public class Permutation {
    	public static int N, R;
    	public static int origin[], number[];
    	public static boolean isSelected[];
    
    	public static void main(String arg[]) throws IOException{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		String input[] = br.readLine().split(" ");
    		N = Integer.parseInt(input[0]);
    		R = Integer.parseInt(input[1]);
    		origin = new int[N];
    		isSelected = new boolean[N];
    		number = new int[R];
    
    		String input2[] = br.readLine().split(" ");
    		for(int i = 0; i < N; i++){
    			origin[i] = Integer.parseInt(input2[i]);
    		}
    		permutation(0);
    	}
    
    	private static void permutation(int idx){
    		if(idx == R){
    			System.out.println(Arrays.toString(number));
    			return;
    		}
    
    		// 해당 자리에 뽑을 가능한 모든 수에 대해 시도
    		for(int i = 0; i < N; i++){
    			if(isSelected[i]) continue;
    			number[idx] = origin[i];
    			isSelected[i] = true;
    			permutation(idx + 1); // 다음 자리의 순열 뽑기
    			isSelected[i] = false;
    		}
    	}    
    }       

     

     

    중복 순열이란 무엇인가?

    서로 다른 N개의 수 중에 중복하여 R개를 선택하여 나열

    n파이R = n^r 로 표현할 수 있습니다.

     


     

    next_permutation이란 무엇인가?

    현재 순열의 상태에서 크기순으로(사전순) 다음에 올 수 있는 순열을 생성해주는 역할을 합니다.

    c++의 경우 라이브러리가 있으나 java의 경우에는 없기 때문에 암기가 어느정도 필요할 것이라고 생각합니다

     

     

    예를 들어 1, 4, 5, 6라는 수가 있을 때

    1 4 5 6 -> 1 4 6 5 -> 1 5 4 6 -> 1 5 6 4 ~ 식으로 순열을 만들어주는 역할을 수행하는 메소드입니다.

     

     

    next_permutation 동작 방식

    1. 가장 작은 순열부터 시작해야합니다. (그래야 모든 순열을 다 생성할 수 있기 때문입니다.)
    2. 하나의 순열을 처리하고 다음 순열을 받아서 데이터를 처리하는 식으로 쓰기 때문에 do - while 형태로 구현합니다.
    3. 메소드 호출로 받은 순열을 사용한 후 next_permutation()을 호출하여 다음 순열을 받습니다.
    4. 이때 next_permutation의 리턴 값은 boolean 값으로 다음 순열을 만들 수 있는지 없는지를 반환해주는 형태로 구현합니다.
    5.  next_permutation
      1. 뒤쪽부터 탐색하며 꼭대기를 찾아야합니다. 
      2. i - 1 위치와 교환할 큰 값을 찾습니다.
      3. 그리고 i - 1과 j의 값을 교환합니다.
      4. 꼭대기부터 뒤까지 오름차순으로 정렬합니다.

     

    next_permutation 구현 방법

    1. 뒤쪽부터 탐색하며 꼭대기를 찾아야합니다. (뒤에서 시작했을 때 오름차순이 끝나는 지점이 꼭대기(i)입니다.)
    2. i - 1 위치와 교환할 큰 값을 찾습니다.(꼭대기(i) 바로 앞자리와 교환할 큰 값을 찾아야합니다.)
    3. i - 1과 j의 값을 교환(교환 후 여전히 꼭대기부터 맨 뒤 원소까지 내림차순으로 되어있습니다.)
    4. 꼭대기부터 뒤까지 오름차순으로 정렬(따로 정렬 알고리즘을 사용할 필요는 없습니다.)

     

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    public class NextPermutation {
    
    	public static int N, origin[];
    	public static void main(String[] args) throws NumberFormatException, IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		N = Integer.parseInt(br.readLine());
    		String input[] = br.readLine().split(" ");
    		origin = new int[N];
    		
    		for(int i = 0 ; i < N; i++) {
    			origin[i] = Integer.parseInt(input[i]);
    		}
    		
    		Arrays.sort(origin);
    		do {
    			System.out.println(Arrays.toString(origin));
    		} while(next_permutation());
    	}
    	
    	private static boolean next_permutation() {
    		int i = N - 1;
    		while(i > 0 && origin[i - 1] >= origin[i]) --i;
    		if(i == 0) return false;
    		
    		int j = N - 1;
    		while(origin[i - 1] >= origin[j]) --j;
    		
    		int tmp = origin[i - 1];
    		origin[i - 1] = origin[j];
    		origin[j] = tmp;
    		
    		int k = N - 1;
    		while(i < k) {
    			tmp = origin[i];
    			origin[i] = origin[k];
    			origin[k] = tmp;
    			++i;
    			--k;
    		}
    		return true;
    	}
    }
    

     

     

    next_permutation은 현재 순열보다 큰 순열을 만들어주기 때문에 중복되는 수의 입력이 들어와도 중복이 제거됩니다.

    1 1 3이 들어왔을 때 6가지의 경우가 나오지만 next_permutation은 3가지 경우만 만들어집니다. 

     

     

     

     

Designed by Tistory.