Exercise: Powerset

Your task is to implement the powerset function, which returns a set of all subsets of a given set. Here are a few examples of how it should work:

powerset(setOf()) == setOf(setOf())
powerset(setOf(1)) == setOf(setOf(), setOf(1))
powerset(setOf(1, 2)) == setOf(
    setOf(), setOf(1), setOf(2), setOf(1, 2)
)
powerset(setOf(1, 2, 3)) == setOf(
    setOf(), setOf(1), setOf(2), setOf(3), setOf(1, 2),
    setOf(1, 3), setOf(2, 3), setOf(1, 2, 3)
)

Here is the starting point:

fun <T> Collection<T>.powerset(): Set<Set<T>> {
    TODO()
}

It is easiest to implement this function using recursion. Notice, that a powerset of a set with n elements is a powerset of a set with n-1 elements, plus all elements from the powerset of a set with n-1 elements with the n-th element added.

powerset(setOf()) == setOf(setOf())

powerset(setOf(1)) ==
    powerset(setOf()) + powerset(setOf()).eachPlus(1)

powerset(setOf(1,2)) ==
    powerset(setOf(1)) + powerset(setOf(1)).eachPlus(2)

powerset(N) == powerset(N/m) + powerset(N/m).eachPlus(m)

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/Powerset.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

// Powerset returns set of all subsets including full set and empty set
// https://en.wikipedia.org/wiki/Power_set
fun <T> Collection<T>.powerset(): Set<Set<T>> {
    TODO()
}

fun main() {
    println(setOf<Int>().powerset()) // [[]]
    println(setOf("A").powerset()) // [[], [A]]
    println(setOf('A', 'B').powerset()) // [[], [B], [A], [B, A]]
    println(setOf(1, 2, 3).powerset())
    // [[], [3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]]
    println(setOf(1, 2, 3, 4).powerset())
    // [[], [4], [3], [4, 3], [2], [4, 2], [3, 2], [4, 3, 2], [1], [4, 1], [3, 1], [4, 3, 1], [2, 1], [4, 2, 1], [3, 2, 1], [4, 3, 2, 1]]
}

class PowersetTest {

    @Test
    fun `Powerset of empty list is only empty list`() {
        val emptyList = setOf<Int>()
        assertEquals(setOf(emptyList), emptyList.powerset())
    }

    @Test
    fun `Powerset of list with single element is empty list and single element`() {
        assertEquals(setOf(setOf(1), setOf()), setOf(1).powerset())
    }

    @Test
    fun `Powerset simple example test`() {
        val set = setOf(
                setOf(1, 2, 3),
                setOf(1, 2),
                setOf(1, 3),
                setOf(2, 3),
                setOf(1),
                setOf(2),
                setOf(3),
                setOf()
        )
        assertEquals(set, setOf(1, 2, 3).powerset())
    }

    @Test
    fun `Size of n element set powerset is 2^n`() {
        for(n in 1..6) {
            val set = (1..n).toSet()
            val size = 2.pow(n)
            assertEquals(size, set.powerset().size)
        }
    }

    private fun Int.pow(power: Int): Int = Math.pow(this.toDouble(), power.toDouble()).toInt()
}