August 26, 2024
P26 - Generate the combinations of K distinct objects chosen from the N elements of a list.
In how many ways can a committee of 3 be chosen from a group of 12 people? There are C(12,3) = 220 possibilities, where C(N,K) denotes binomial coefficient. For pure mathematicians, this result may be great. But we want to really generate all the possibilities. Example:
> combinations(3, "abcde".toList())
[[c, b, a], [d, b, a], [e, b, a], [d, c, a], [e, c, a], [e, d, a], [d, c, b], [e, c, b], [e, d, b], [e, d, c]]kotlin
package org.kotlin99.lists
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Test
import org.kotlin99.common.containsAll
import org.kotlin99.common.tail
fun <T> combinations(n: Int, list: List<T>): List<List<T>> =
if (n == 0) listOf(emptyList())
else list.flatMapTails { subList ->
combinations(n - 1, subList.tail()).map { (it + subList.first()) }
}
private fun <T> List<T>.flatMapTails(f: (List<T>) -> (List<List<T>>)): List<List<T>> =
if (isEmpty()) emptyList()
else f(this) + this.tail().flatMapTails(f)
class P26Test {
@Test fun `generate the combinations of K distinct objects chosen from the N elements of a list`() {
assertThat(combinations(0, "abc".toList()), equalTo(listOf(emptyList())))
assertThat(combinations(1, "abc".toList()), containsAll(listOf(
"a".toList(), "b".toList(), "c".toList()
)))
assertThat(combinations(2, "abc".toList()), containsAll(listOf(
"cb".toList(), "ab".toList(), "ca".toList()
)))
assertThat(combinations(3, "abc".toList()), containsAll(listOf(
"cba".toList()
)))
assertThat(combinations(3, "abcde".toList()), containsAll(listOf(
"cba".toList(), "dba".toList(), "eba".toList(),
"dca".toList(), "eca".toList(), "eda".toList(),
"dcb".toList(), "ecb".toList(), "edb".toList(),
"edc".toList()
)))
assertThat(combinations(3, "abcdefghijkl".toList()).size, equalTo(220))
}
}
Be first to comment