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)
    }
}