순열(Permutation)
서로 다른 n개를 가진 원소에서 r개를 중복없이 골라 순서대로 나열한다.
조합에서 확장된 개념으로, 조합과 달리 순서가 있다.
방문 여부 배열을 이용한 처리 과정
- 깊이 우선 탐색(DFS, Depth-First Search)으로 모든 원소를 방문한다.
- 방문 여부를 확인하여 값이 중복되지 않게 한다.
- 깊이가 r과 일치할 때까지 위 과정을 반복한다.
코드 1. n!
Kotlin
private const val alphabets = "ABC"
private lateinit var result: Array<Char> // 정렬된 알파벳
private lateinit var visited: Array<Boolean> // 순열 방문 여부
fun main() {
result = Array(alphabets.length) { '_' }
visited = Array(alphabets.length) { false }
permutation()
}
fun permutation(depth: Int = 0) {
if (depth == alphabets.length) {
println(result.contentDeepToString()) // 완성된 순열
return
}
for (i in alphabets.indices) {
if (visited[i]) continue
result[depth] = alphabets[i]
visited[i] = true
permutation(depth + 1)
visited[i] = false
}
}코드 2. nPr + 제네릭 타입으로 모든 데이터 타입 대응
Kotlin
fun main() {
permutation(arrayOf("A", "B", "C"), 3).forEach {
println(it)
}
}
/**
* 순열
*
* @param elements: n개 원소를 가진 배열
* @param r: 추출할 원소 수
*/
fun <T> permutation(elements: Array<T>, r: Int): List<List<T>> {
val visited = BooleanArray(elements.size) // 방문 여부
val results = mutableListOf<List<T>>() // 모든 경우의 수
val result = elements.sliceArray(0 until r) // r개를 정렬한 결과
fun recursionPermutation(depth: Int = 0) {
if (depth == r) {
results.add(result.toList())
return
}
for (i in elements.indices) {
if (visited[i]) continue
visited[i] = true
result[depth] = elements[i]
recursionPermutation(depth + 1)
visited[i] = false
}
}
recursionPermutation()
return results
}코드 3. nPr + swap을 이용한 처리
Kotlin
fun main() {
permutation(arrayOf("A", "B", "C"), 3).forEach {
println(it)
}
}
fun <T> permutation(elements: Array<T>, r: Int): List<List<T>> {
val n = elements.size
val results = mutableListOf<List<T>>() // 모든 경우의 수
fun swapPermutation(depth: Int = 0) {
if (depth == r) {
results.add(elements.takeLast(r).toList())
return
}
for (i in range(depth, n)) {
var tmp = elements[i]
elements[i] = elements[depth]
elements[depth] = tmp
swapPermutation(depth + 1)
// 원위치
tmp = elements[i]
elements[i] = elements[depth]
elements[depth] = tmp
}
}
swapPermutation()
return results
}결과
Plain Text
[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]Reference
https://velog.io/@chayezo/Algorithm-순열-조합
https://hanyeop.tistory.com/455
https://notepad96.tistory.com/111
https://programming4myself.tistory.com/94
https://velog.io/@soyeon207/알고리즘-순열-yaxs0hh7
https://gyeong-log.tistory.com/51
https://soopeach.tistory.com/157
https://velog.io/@heyday_7/알고리즘-순열과-조합
