[Kotlin] Algorithm - Combination
Kotlin2023-10-06 18:53 (KST)
Language :
Combination
Choose r from different n elements without duplication and list them in order.
![ncr.png](https://file.dico.me/2023/09/20230926111928_000.png)
Process
- Select (fixed) an element from the array.
- Find and paste the combination based on the remaining arrangements.
- Repeat the above procedure until the number of combined elements (recursive call depth) matches r.
![ncr_01.jpg](https://file.dico.me/2023/09/20230926153725_000.jpg)
The number of all three combinations in an array [A, B, C, D]
Code 1
private const val alphabets = "ABC"
private val results = mutableListOf<Char>() // Altered Alphabet
fun main() {
combination(2)
}
/**
* Combination
* @param count: Number to be extracted
* @param index: The index to begin the search. Numbers already extracted do not need to be checked again because they do not take into account the order.
* @param depth: Number of Extracted
*/
fun combination(count: Int = 0, index: Int = 0, depth: Int = 0) {
if (depth == count) {
println("[${results.joinToString(", ")}]") // a complete combination
return
}
for (i in index until alphabets.length) {
results.add(alphabets[i])
combination(count, i + 1, depth + 1)
results.removeAt(results.lastIndex)
}
}
Code 2. Compatible with all data types with generic types
fun main() {
combination(arrayOf("A", "B", "C"), 2).forEach {
println(it)
}
}
fun <T> combination(elements: Array<T>, r: Int): List<List<T>> {
val n = elements.size
val results = mutableListOf<List<T>>() // the number of all cases
val result = elements.sliceArray(0 until r)
fun recursionCombination(depth: Int = 0, index: Int = 0) {
if (depth == r) {
results.add(result.toList())
return
}
for (i in index until n) {
result[depth] = elements[i]
recursionCombination(depth + 1, i + 1)
}
}
recursionCombination()
return results
}
Result
[A, B]
[A, C]
[B, C]
Reference
https://velog.io/@chayezo/Algorithm-순열-조합
https://hanyeop.tistory.com/455
https://notepad96.tistory.com/111
https://gyeong-log.tistory.com/51
https://soopeach.tistory.com/157
https://velog.io/@heyday_7/알고리즘-순열과-조합
Previous Article
[Kotlin] Algorithms - Permutation
Kotlin