article banner

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