Power Set in Kotlin

by

The power set of a set A, denoted by P(A), is the set of all subsets of A, including the empty set and A itself.

For example, if A = {1, 2}, then P(A) = { {}, {1}, {2}, {1,2} }.

The power set of a set can be useful in various areas of mathematics, computer science, and statistics, such as in set theory, combinatorics, and probability theory.

To find the power set of a set, you can use the following algorithm:

  1. Initialize an empty set S to represent the power set.
  2. For each element x in the original set A, create a new set that contains only x, and add it to S.
  3. For each element x in A, and for each subset Y in S that does not already contain x, create a new set that is the union of Y and {x}, and add it to S.
  4. The power set of A is now stored in S.
Kotlin
fun main() {
    val setA = setOf(1, 2, 3)
    val powerSet = getPowerSet(setA)
    println(powerSet)
}

fun getPowerSet(setA: Set<Int>): Set<Set<Int>> {
    if (setA.isEmpty()) {
        return setOf(setOf())
    } else {
        val element = setA.first()
        val rest = setA.minus(element)
        val powerSetWithoutElement = getPowerSet(rest)
        val powerSetWithElement = powerSetWithoutElement.map { it + element }
        return powerSetWithoutElement.union(powerSetWithElement)
    }
}

This code defines a set setA and then calls the getPowerSet function to find the power set of setA. The getPowerSet function uses recursion to find the power set. If the input set is empty, the function returns a set that contains only the empty set. Otherwise, it selects an arbitrary element from the set, computes the power set of the rest of the set (without the selected element) using recursion, and combines the resulting sets to form the final power set.

Output:

[{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]

Leave a Comment