순열이란?
수학에서 순열(Permutation) 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다. 즉, n 이하의 양의 정수들을 곱한 값이다. 쉽게 말하자면 서로 다른 n개중에서 r개를 선택하는 경우의 수이다.
1. Swap 을 이용한 순열
첫번째는 swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법이다.
배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap 한다.
depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고
depth 보다 인덱스가 큰 값들만 가지고 다시 swap 을 진행한다.
하지만 이 방식은 사전 순으로 경우의 수를 찾지 않기 때문에 순열들의 순서가 보장되지 않는다.
val num = intArrayof(1, 2, 3)
val output = mutableListOf<Int>()
val visited = BooleanArray(num.size)
fun main() {
permutation(3, 3)
}
fun permutation(cnt : Int, depth : Int) {
if (depth == cnt) {
print(num, cnt)
return
}
for (i in depth until num.size) {
swap(depth, i)
permutation(cnt, depth + 1)
swap(depth, i)
}
}
fun swap(depth : Int, i : Int) {
var temp = num[depth]
num[depth] = num[i]
num[i] = temp
}
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
2. Visited 배열을 이용한 순열
두번째로는 visited 배열을 이용하는 방법이다.
1번과 달리 사전식으로 순열을 구현할 수 있다.
Visited 배열을 이용한 순열은 visited 라는 BooleanArray를 이용해서 해당 인덱스를 방문했는지를 묻게된다.
DFS를 돌면서 모든 인덱스를 방문하고 output에 결과값을 넣게된다.
val num = intArrayof(1, 2, 3)
val output = mutableListOf<Int>()
val visited = BooleanArray(num.size)
fun main() {
permutation(3, 3)
}
fun permutation(cnt: Int, depth: Int) {
if (cnt == depth) {
print("$output")
return
}
for (i in 0 until num.size) {
if(visited[i] == false) {
visited[i] = true
output.add(num[i])
permutation(cnt + 1, depth)
add.removeAt(num.lastIndex)
visited[i] = false
}
}
}
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
조합이란?
집합에서 서로 다른 n개의 값 중에서 r 개의 숫자를 순서를 고려하지 않고 나열한 경우의 수이다.
순열과는 순서를 고려하지 않는다는 점이 다르다고 할 수 있다.
ex) 1, 2, 3
1개 선택 - (1), (2), (3)
2개 선택 - (1, 2), (1, 3), (2, 3)
3개 선택 - (1, 2, 3)
fun main() {
var num = listOf(1, 2, 3)
for(i in 1 .. num.size) {
val answer = mutableListOf<List<Int>>()
println("================$i 개====================")
combination(answer, num, Array<Boolean>(num.size) { false }, 0, i)
answer.forEach { println(it) }
}
}
fun combination(answer: MutableList<List<T>>, el: List<T>, ck: Array<Boolean>, start: Int, target: Int) {
if(target == 0) {
answer.addAll( listOf(el.filterIndexed { index, t -> ck[index] }) )
} else {
for(i in start until el.size) {
ck[i] = true
combination(answer, el, ck, i + 1, target - 1)
ck[i] = false
}
}
}
Reference
https://rutgo-letsgo.tistory.com/221
https://bcp0109.tistory.com/14
https://medium.com/depayse/kotlin-%EC%88%9C%EC%97%B4-permutation-36e85898896c
'개발자의 기본 소양 > ALGORITHM' 카테고리의 다른 글
Floyd-Warshall Algirithm (플로이드 워셜 알고리즘) (0) | 2023.02.23 |
---|---|
Dijkstra Algorithm (다익스트라 알고리즘) with 프로그래머스 - 배달 (0) | 2023.02.23 |
Brute Force (완전탐색) (0) | 2023.02.13 |
DFS와 BFS with 백준 1260번: DFS와 BFS (0) | 2023.01.17 |
알고리즘과 설계기법 (0) | 2022.11.30 |