[알고리즘 정리] 순열, next_permutation 구현

 

 

다룰 내용

• 순열이란 무엇인가?
• 순열 구현
• 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가지 경우만 만들어집니다.