Exercise: All possible partitions of a set
Your task is to implement the partitions function, which returns a set of all possible partitions of a given set. A partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset. Here are a few examples of how it should work:
partitions(setOf(1)) == setOf(setOf(setOf(1)))
partitions(setOf(1, 2)) == setOf(
setOf(setOf(1), setOf(2)),
setOf(setOf(1, 2))
)
partitions(setOf(1, 2, 3)) == setOf(
setOf(setOf(1), setOf(2), setOf(3)),
setOf(setOf(1), setOf(2, 3)),
setOf(setOf(1, 2), setOf(3)),
setOf(setOf(1, 2, 3))
)Here is the starting point:
fun <T> Collection<T>.partitions(): Set<Set<Set<T>>> = TODO()
It is easiest to implement this function using recursion.
This problem can either be solved in the below playground or you can clone kotlin-exercises project and solve it locally. In the project, you can find code template for this exercise in functional/collections/Partitions.kt. You can find there starting code and unit tests.
Once you are done with the exercise, you can check your solution here.
Playground
import org.junit.Test
import kotlin.test.assertEquals
fun <T> Collection<T>.partitions(): Set<Set<Set<T>>> = TODO()
class PartitionsTest {
@Test
fun `partitions of two elements`() {
val result = setOf(1, 2).partitions()
val expected = setOf(
setOf(setOf(1), setOf(2)),
setOf(setOf(1, 2))
)
assertEquals(expected, result)
}
@Test
fun `partitions of three elements`() {
val result = listOf("A", "B", "C").partitions()
val expected = setOf(
setOf(setOf("A"), setOf("B"), setOf("C")),
setOf(setOf("A"), setOf("B", "C")),
setOf(setOf("A", "B"), setOf("C")),
setOf(setOf("A", "C"), setOf("B")),
setOf(setOf("A", "B", "C"))
)
assertEquals(expected, result)
}
@Test
fun `partitions of four elements`() {
val result = listOf("A", "B", "C", "D").partitions()
val expected = setOf(
setOf(setOf("D"), setOf("C"), setOf("B"), setOf("A")),
setOf(setOf("D", "C"), setOf("B"), setOf("A")),
setOf(setOf("C"), setOf("D", "B"), setOf("A")),
setOf(setOf("D"), setOf("C", "B"), setOf("A")),
setOf(setOf("D", "C", "B"), setOf("A")),
setOf(setOf("C"), setOf("B"), setOf("D", "A")),
setOf(setOf("D"), setOf("B"), setOf("C", "A")),
setOf(setOf("D"), setOf("C"), setOf("B", "A")),
setOf(setOf("B"), setOf("D", "C", "A")),
setOf(setOf("D", "C"), setOf("B", "A")),
setOf(setOf("D", "B"), setOf("C", "A")),
setOf(setOf("C"), setOf("D", "B", "A")),
setOf(setOf("C", "B"), setOf("D", "A")),
setOf(setOf("D"), setOf("C", "B", "A")),
setOf(setOf("D", "C", "B", "A"))
)
assertEquals(expected, result)
}
}
