조합(Combination)
서로 다른 n개를 가진 원소에서 r개를 중복없이 골라 순서없이 나열한다.
과정
- 배열에서 원소 하나를 선택(고정)한다.
- 나머지 배열을 기준으로 조합을 구하여 붙인다.
- 조합된 원소 개수(재귀호출 깊이)가 r과 일치할 때까지 위 과정을 반복한다.
코드 1
private const val alphabets = "ABC"
private val results = mutableListOf<Char>() // 정렬된 알파벳
fun main() {
combination(2)
}
/**
* 조합
* @param count: 추출할 개수
* @param index: 탐색을 시작할 인덱스. 순서를 고려하지 않으므로 이미 추출된 숫자는 다시 확인할 필요가 없다.
* @param depth: 추출된 개수
*/
fun combination(count: Int = 0, index: Int = 0, depth: Int = 0) {
if (depth == count) {
println("[${results.joinToString(", ")}]") // 완성된 조합
return
}
for (i in index until alphabets.length) {
results.add(alphabets[i])
combination(count, i + 1, depth + 1)
results.removeAt(results.lastIndex)
}
}
코드 2. 제네릭 타입으로 모든 데이터 타입 대응
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>>() // 모든 경우의 수
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
}
결과
[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/알고리즘-순열과-조합