[알고리즘] 순열 - java(백준 10972/10973/10974/1722)

순열

"1~N 까지 겹치는 숫자가 없이 나열되어있는 것"

크기가 N인 수열은 총 N! 개

N의 범위에 따라 자료형(int, long)으로 적절히 선언해주어야 한다.

사전 식 나열 -> "오름 차순 정렬"

다음순열(next_premutation in C++ STL) - O(n)

• A[i-1]<A[i]를 만족하는 가장 큰 i -> 가장 마지막부터 시작하는 가장 긴 감소수열을 찾음 O(n)

결과적으로 A[0]A[1]...A[i-1]로 시작하는 가장 마지막 순열이 됨

• j>=i 이면서 A[j]>A[i-1]를 만족하는 가장 큰 j 를 찾음

i번째 부터 내림 차순 정렬된 상태이기 때문에, i 번째부터 끝까지 중 에서 i-1보다 크면서 가장 작은 수가 선택

• A[i-1]과 A[j] swap

A[0]..A[i-1] 의 다음순열로 바뀌게 됨

• A[i]부터 순열을 뒤집음 O(n)

내림차순 -> 오름차순으로 바꿈으로써, A[0]A[1]...A[i-1(전 A[j])]로 시작하는 가장 작은 순열이 됨

#백준 10972번 다음순열

    import java.util.Scanner;
    
    public class Main {
    	
    	public static boolean next_premutation(int[] arr, int s, int e){
    		
    		//arr[i-1] < arr[i]를 만족하는 가장 큰 i
    		int i=e-1;
    		for(; i>s; i--){			
    			if(arr[i-1] >arr[i])
    				continue;
    			else
    				break;
    		}
    		if(i==0) return false;//이미 내림차순 정렬 완료된 상태 -> 가장 마지막 순열
    
    		//i<=j를 만족하고, A[j]>A[i-1]를 만족하는 가장 큰 j
    		int j=e-1;
    		for(; j>=i; j--){
    			if(arr[j]<arr[i-1])
    				continue;
    			else
    				break;
    		}
    	
    		
    		//A[i-1], A[j] swap
    		int tmp=arr[i-1];
    		arr[i-1]=arr[j];
    		arr[j]=tmp;
    		//1234567
    		//i부터 끝까지 뒤집음 
    		j=e-1;
    		while(i<j){
    			int temp=arr[i];
    			arr[i]=arr[j];
    			arr[j]=temp;
    			i++; j--;
    		}
    		return true;
    	}
    	
    	public static void main(String[] args){
    		Scanner scan=new Scanner(System.in);
    		int N=scan.nextInt();
    		int[] premutation=new int[N];
    		for(int i=0; i<N; i++)
    			premutation[i]=scan.nextInt();
    		
    		if(next_premutation(premutation, 0, N)){
    			for(int i=0; i<N; i++)
    				System.out.print(premutation[i]+" ");
    			System.out.println();
    		}else
    			System.out.println(-1);
    		
    	}
    
    }

이전순열(pre_premutation in STL C++)

• A[i-1] > A[i] 인 가장 큰 i

뒤에서부터 가장 긴 증가순열을 찾음

• j>=i 를 만족하고 A[i-1]>A[j] 인 가장 큰 j

i번째부터 n까지 중 A[i-1]보다 작은 것 중 가장 큰 j

• A[i-1]과 A[j] swap

• A[i]부터 끝까지 뒤집기

증가순열 -> 감소순열

#백준 10973번 이전순열

import java.util.Scanner;

public class Main {
	       public static boolean pre_premutation(int[] arr, int s, int e){
		int i=e-1;
		
		//최대 길이의 오름차순 
		for(; i>0; i--){
			if(arr[i]> arr[i-1])
				continue;
			else
				break;
		}
		//이미 오름차순 정렬 -> 가장 첫번째 수열 
		if(i==0) return false;

		//i<=j를 만족하고, A[j]>A[i-1]를 만족하는 가장 큰 j
		int j=e-1;
		for(; j>=i; j--){
			if(arr[j]>arr[i-1])
				continue;
			else
				break;
		}		
		//A[i-1], A[j] swap
		int tmp=arr[i-1];
		arr[i-1]=arr[j];
		arr[j]=tmp;
		//1234567
		//i부터 끝까지 뒤집음 
		j=e-1;
		while(i<j){
			int temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
			i++; j--;
		}
		return true;
	}
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		int N=scan.nextInt();
		int[] premutation=new int[N];
		for(int i=0; i<N; i++)
			premutation[i]=scan.nextInt();
		
		if(pre_premutation(premutation, 0, N)){
			for(int i=0; i<N; i++)
				System.out.print(premutation[i]+" ");
			System.out.println();
		}else
			System.out.println(-1);		
	}
}

모든순열

next_premutation이나 pre_premutation은 다음 순열이 존재하는지의 여부를 위해 반환 타입을 boolean으로 지정한다.

이것을 이용해서 모든 수열을 구할 수 있다.

#백준 10974번 모든순열

import java.util.Scanner;

public class Main {	
	public static boolean next_premutation(int[] arr, int s, int e){		
		//arr[i-1] < arr[i]를 만족하는 가장 큰 i
		int i=e-1;
		for(; i>s; i--){			
			if(arr[i-1] >arr[i])
				continue;
			else
				break;
		}
		if(i==0) return false;

		//i<=j를 만족하고, A[j]>A[i-1]를 만족하는 가장 큰 j
		int j=e-1;
		for(; j>=i; j--){
			if(arr[j]<arr[i-1])
				continue;
			else
				break;
		}
	
		//A[i-1], A[j] swap
		int tmp=arr[i-1];
		arr[i-1]=arr[j];
		arr[j]=tmp;
		//1234567
		//i부터 끝까지 뒤집음 
		j=e-1;
		while(i<j){
			int temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
			i++; j--;
		}
		return true;
	}
	
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		int N=scan.nextInt();
		int[] premutation=new int[N];
		for(int i=0; i<N; i++)
			premutation[i]=i+1;
		
		do{
			for(int i=0; i<N; i++)
				System.out.print(premutation[i]+" ");
			System.out.println();
		}while(next_premutation(premutation, 0, N));	
	}
}

"순열의 크기가 N일 때"

1) 특정 순열이 주어지고, 몇 번째 순열인지?

크기가 N인 순열은 총 N!개

N=6이고 알고 싶은 순열이 3 O O O O O 라면,

1 O O O O O -> 5!개

2 O O O O O -> 5! 개

2*5!를 더하는 것으로 시작한다.

이 규칙을 이용한다.

#백준 1722번

	public static long order_premutation(int[] arr){
                //순열 arr이 주어진다. 
		Set<integer> set=new HashSet<>();
                //현재 검사하고 있는 위치의 이전에 있는 숫자는 고려할 필요가 없음으로 중복 확인을 위한 Set을 선언한다.
		long count=0;
               //주어지는 N에 따라 int/long을 선언한다.
		int k;//순열 i번째 값까지 지나는 수를 의미한다.
		for(int i=0; i<arr.length; i++){
			for(k=1; k<arr[i]; k++){				
				if(!set.contains(k))		
					count+=factorial[arr.length-i-1];
			}
			set.add(k);
		}	
		return count+1;

2) 몇 번째 순열인지 주어지고, 이 순열은 무엇인지?

public static int[] nth_premutation(long N,int size){
		Set<Integer> set=new HashSet<>();
		int[] arr=new int[size];
		//N번째 순열 , size 
		int i;
		for(i=0; i<size; i++){	
		    for(int j=1; j<=size; j++){
                if(set.contains(j)) continue;
                if(factorial[size-i-1]<N){
                    N-=factorial[size-i-1];
                }else{
                    arr[i]=j;
                    set.add(j);
                    break;
                }
            }	
		}		
		return arr; 
	}