순열
순열이란 n 개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말한다.
수학에서 순열은 서로 다른 n개의 원소에서 r개를 뽑아한 줄로 세우는 경우의 수이다. 순열의 개수는 n의 계승 n! 와 같다.
예를 들어 [1, 2, 3] 배열에서 2개의 숫자를 뽑는 순열은
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]참고
순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다.
말 그대로, 순서가 존재하는 열이라는 것이다.
즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 등.. 모두 다른 결과를 가져온다. 순서가 다르기 때문이다.
조합은 순서가 상관이 없는 모임을 의미한다. 순서가 상관없기 때문에
{ 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은 것으로 취급을 한다. 순서가 상관없기 때문에
1, 2, 3 이라는 3개의 숫자로 이루어져 있다는 점에서 똑같은 취급을 하는 것이 조합이다.
구현
아래 블로그를 참고했습니다.
순열 Permutation (Java)
순열 연습 문제 순열이란 n 개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말합니다. 예를 들어 [1, 2, 3] 이라는 3 개의 배열에서 2 개의 숫자를 뽑는 경우는 [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3
bcp0109.tistory.com
- arr : r개를 뽑기 위한 n개의 값이 저장된 배열
- output : 뽑힌 r개의 값을 저장하는 배열
- visited : 중복해서 뽑지 않기 위해 방문했는지를 체크하는 배열
int[] arr = {1, 2, 3}; //순열을 만들 배열
int n = arr.length; //배열의 길이
int[] output = new int[n]; //순열 출력을 위한 배열
boolean[] visited = new boolean[n]; //중복해서 뽑지 않기 위해 방문했는지를 체크하는 배열
//1. Swap 함수를 이용해 구현
per1(arr, 0, n, 3);
//2. DFS를 이용해 구현
per2(arr, output, visited, 0, n, 3); //r = 3, 3개를 뽑을 것
1. SWAP을 이용해 구현
배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한 번씩 swap 한다.
depth를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고, depth 보다 인덱스가 큰 값들만 가지고 다시 swap을 진행한다.
순열들의 순서가 보장되지 않는다.
//1. Swap 함수를 이용해 구현 - 순서 없이 n 개중에서 r 개를 뽑는 경우
static void per1(int[] arr, int depth, int n, int r) {
if(depth == r) {
print(arr, r);
return;
}
for(int i=depth; i<n; i++) {
swap(arr, depth, i);
per1(arr, depth + 1, n, r);
swap(arr, depth, i);
}
}
static void swap(int[] arr, int depth, int i) { //두 배열의 값을 바꾸는 Swap 함수
int temp = arr[depth];
arr[depth] = arr[i];
arr[i] = temp;
}2. Visited 배열을 이용해 DFS로 구현
1번과 달리 순서를 지켜 순열을 출력할 수 있다.
DFS로 모든 인덱스를 방문하며 output에 값을 넣는다.
이미 들어간 값은 visited 값을 true로 바꾸어 중복하여 넣지 않는다.
depth 값은 output에 들어간 숫자의 길이라고 생각하면 된다.
depth의 값이 r만큼 되면 output에 들어있는 값을 출력한다.
//2. DFS를 이용해 구현 - 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
static void per2(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
if(depth == r) {
print(output, r); //순열 출력을 위한 print 함수
return;
}
for(int i = 0; i < n; i++) {
if(visited[i] != true) {
visited[i] = true;
output[depth] = arr[i];
per2(arr, output, visited, depth + 1, n, r);
visited[i] = false;
}
}
}
3. 순차적인 숫자만으로 이루어진 순열을 구할 경우
0, 1, 2, 3 or 1, 2, 3, 4 or 5, 7, 9, 11과 같이 단순히 오름차순으로 숫자만을 가지는 순열을 구하고 싶은 경우
arr, visited 배열 없이 단순하게 구현할 수 있다.
for문에서 순열을 시작할 숫자 i부터 끝 범위를 지정하면 된다. (i++부분을 i+=2와 같이 바꾸면 건너뛰어 구해줄 수도 있다.)
public static void per3(int depth, int r) {
if(depth == r) {
// 순열 출력
for(int n : output) {
System.out.print(n + " ");
}
System.out.println();
return;
}
for(int i = 0; i < 4; i++) { // 0, 1, 2, 3 숫자 중에서 r개의 순열을 뽑음
output[depth] = i;
per3(depth+1, r);
}
}
전체 코드
public class Permutation {
public static void main(String[] args) {
int[] arr = {1, 2, 3}; //순열을 만들 배열
int n = arr.length; //배열의 길이
int[] output = new int[n]; //순열 출력을 위한 배열
boolean[] visited = new boolean[n]; //중복해서 뽑지 않기 위해 방문했는지를 체크하는 배열
System.out.println("-------- 1. Swap ---------");
per1(arr, 0, n, 3);
System.out.println("\n-------- 2. DFS ---------");
per2(arr, output, visited, 0, n, 3); //r = 3, 3개를 뽑을 것
}
//1. Swap 함수를 이용해 구현 - 순서 없이 n 개중에서 r 개를 뽑는 경우
static void per1(int[] arr, int depth, int n, int r) {
if(depth == r) {
print(arr, r);
return;
}
for(int i = depth; i < n; i++) {
swap(arr, depth, i);
per1(arr, depth + 1, n, r);
swap(arr, depth, i);
}
}
static void swap(int[] arr, int depth, int i) { //두 배열의 값을 바꾸는 Swap 함수
int temp = arr[depth];
arr[depth] = arr[i];
arr[i] = temp;
}
//2. DFS를 이용해 구현 - 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
static void per2(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
if(depth == r)
print(output, r); //순열 출력을 위한 print 함수
return;
}
for(int i = 0; i < n; i++) {
if(visited[i] != true) {
visited[i] = true;
output[depth] = arr[i];
per2(arr, output, visited, depth + 1, n, r);
visited[i] = false;
}
}
}
// 배열 출력
static void print(int[] arr, int r) {
for(int i = 0; i < r; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
출력
-------- 1. Swap ---------
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
-------- 2. DFS ---------
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 연습문제
https://www.acmicpc.net/problem/10974
GITHUB
github.com/KwonMinha/Algorithm/blob/master/Permutaion_Combination/src/Permutation.java
KwonMinha/Algorithm
Contribute to KwonMinha/Algorithm development by creating an account on GitHub.
github.com
관련 포스트
[Java] 조합 Combination
추천 포스트
Java로 작성된 조합, 중복 조합, 순열, 중복 순열과 관련된 포스트이다.
LinkedList 사용해 구현되었고 리스트안에 n까지 값이 순서대로 주어진다.
예를 들어 input : 3 2 라면
(0, 1, 2) 3개의 리스트가 생성되고, 그 중 2개를 뽑아 조합, 중복 조합, 순열, 중복 순열을 만든다.
limkydev.tistory.com/178 [[Java] 조합, 중복조합, 순열, 중복순열 소스]
import java.util.LinkedList;
import java.util.Scanner;
public class PerComb {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //숫자 개수
int r = sc.nextInt(); //뽑을 개수
System.out.println("원소 개수 : " + n + ", 뽑을 개수 : " + r);
System.out.print("( ");
for(int i = 0; i < n; i++) {
System.out.print(i + " ");
}
System.out.println(")");
//순열 (순서있게 배열)
System.out.println("\n순열");
LinkedList<Integer> perArr = new LinkedList<Integer>();
int[] perCheck = new int[n];
permutation(n, r, perArr, perCheck);
//중복순열 (순서있게 배열 + 자기 자신도 포함)
System.out.println("\n중복순열");
LinkedList<Integer> rePerArr = new LinkedList<Integer>();
rePermutation(n, r, perArr);
//조합 (순서 관심 없고 뽑은 유무만 생각)
System.out.println("\n조합");
int[] comArr = new int[r];
combination(comArr, n, r, 0, 0);
//중복 조합 (순서 관심 없고 뽑은 유무만 생각 + 자기 자신도 포함)
System.out.println("\n중복조합");
int[] reComArr = new int[r];
reCombination(reComArr, n, r, 0, 0);
}
//순열(순서있게 배열)
private static void permutation(int n, int r, LinkedList<Integer> perArr, int[] perCheck) {
if(perArr.size() == r){
for(int i : perArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
for(int i=0; i<n; i++){
if(perCheck[i] == 0){
perArr.add(i); //값을 넣는 부분
perCheck[i] = 1;
permutation(n, r, perArr, perCheck);
perCheck[i] = 0;
perArr.removeLast();
}
}
}
//중복순열 (순서있게 배열 + 자기 자신도 포함)
private static void rePermutation(int n, int r, LinkedList<Integer> rePerArr) {
if(rePerArr.size() == r){
for(int i : rePerArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
for(int i=0; i<n; i++){
rePerArr.add(i);
rePermutation(n, r, rePerArr);
rePerArr.removeLast();
}
}
//조합 (순서 관심 없고 뽑은 유무만 생각)
private static void combination(int[] comArr, int n, int r, int index, int target) {
if(r==0){
for(int i : comArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
if(target == n)return;
comArr[index] = target;
combination(comArr, n, r-1, index+1, target+1); //뽑는 경우
combination(comArr, n, r, index, target+1); //안 뽑는 경우
}
//중복 조합 (순서 관심 없고 뽑은 유무만 생각 + 자기 자신도 포함)
private static void reCombination(int[] reComArr, int n, int r, int index, int target) {
if(r==0){
for(int i : reComArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
if(target == n)return;
reComArr[index] = target;
reCombination(reComArr, n, r-1, index+1, target);//뽑는 경우
reCombination(reComArr, n, r, index, target+1);//안 뽑는 경우
}
}참고
bcp0109.tistory.com/14 [순열 Permutation (Java)]
https://ko.wikipedia.org/wiki/순열
'Algorithm' 카테고리의 다른 글
| [Java] DFS로 모든 이동 경로 구하기 (0) | 2020.09.23 |
|---|---|
| [Java] 조합 Combination (6) | 2020.05.12 |
| [Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현 (1) | 2020.05.09 |
| [Java] Graph 그래프 / 인접 행렬 / 인접 리스트 (0) | 2020.05.09 |
| [Java] DFS 깊이 우선 탐색 - 인접리스트 / 인접행렬로 구현 (0) | 2020.04.25 |
댓글