[Algorithm] 순열(permutation) for JAVA

 

순열

 

순열이란 n개의 원소 중에 r개를 순서를 고려해 뽑는 방법이다.

 

 

 

예를 들어 [1,2,3] 이 있을 때 2개를 뽑는다면 n = 3, r = 2가 될 것이고 표현은 3P2 라고 한다.

 

 

[1, 2]

[1, 3]

[2 ,1]

[2, 3]

[3, 1]

[3, 2]

 

 

 

6개가 나올 것이고 원소의 개수는 n! 개이다.

 

 

 

나는 DFS로 이것을 표현할 것이다~

 

 

출처 : https://minhamina.tistory.com/37

 

 

 

DFS로 순열을 표현하면 위의 순서를 따르며 진행될 것이다.

 

 

 

코드

static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) 
   // arr[] = {1,2,3}
   // output[] = 만들어진 원소 ex) {2,1,3} 등
   // visited[] = 위 그림에서 output[0] = 1이고 나머지는 비어있다면 
   //           [0]은 들른거임 그래서 output[1]에 원소 넣는 식으로 진행
   // depth = 그림을 보면 알 수 있는 깊이를 나타낸다. 원소에 넣을 순서를 나타내기도 함
   // n = arr.length , r = 다들 알겠지


   {
	if(depth == r) {
		print(output, r); // 만들어진 원소 출력
		return;
	}

	for(int i = 0; i < n; i++) {
		if(visited[i] != true) {
			visited[i] = true;
			output[depth] = arr[i];
			permutation(arr, output, visited, depth + 1, n, r);    
			visited[i] = false; // 방문한곳 리셋
		}
	}
}

 

 

 

 

 

 

output = 123인게 진행되는 과정을 살펴보면

 

 

 

 

 

 

이렇게됨!

 

 

 

DFS만 살펴보았는데

 

 

 

https://minhamina.tistory.com/37

[Java] 순열 Permutation

 

 

 

이 블로그에 가면 swap으로 바꿔가며 하는 방법과 1234 이나 4567 처럼

 

 

단순 오름차순 중에 순열을 구할 때에는 visited[] 를 굳이 사용하지 않고 하는 방법도 블로그에 나와있다.

 

 

설명 좋아요~~!! 순열도 코테에 자주 나오니 잘 알아둬야지!!