Power Set using Bit Manipulation in Kotlin

by

In set theory, the power set (or the “set of all subsets”) of a given set is defined as the set of all possible subsets of that set, including the empty set and the set itself.

For example, if we have a set A = {1, 2}, the power set of A would be:

P(A) = { {}, {1}, {2}, {1,2} }

Here, the set { } represents the empty set, and each of the other sets represents a subset of the original set A. The power set of A contains 2^n elements, where n is the number of elements in the original set A.

Power Set Using Bit manipulation in Kotlin

Kotlin
fun powerSet(set: IntArray): List<Set<Int>> {
    val n = set.size
    val powSetSize = 1 shl n
    val powerSet = mutableListOf<Set<Int>>()

    for (i in 0 until powSetSize) {
        val subset = mutableSetOf<Int>()
        for (j in 0 until n) {
            if (i and (1 shl j) != 0) {
                subset.add(set[j])
            }
        }
        powerSet.add(subset)
    }

    return powerSet
}

The algorithm works by first calculating the size of the power set, which is 2^n. It then loops through all possible binary numbers from 0 to pow_set_size – 1, where each binary number represents a unique subset of the original set. For each binary number, the algorithm checks the bit at each position and adds the corresponding element to a new subset if the bit is set. Finally, the algorithm adds the subset to the power set and returns it once all subsets have been generated.

  1. Start by defining a function powerSet that takes an input integer array set and returns a list of sets representing the power set of the input set.
  2. Get the size n of the input set using the size property of the IntArray class.
  3. Calculate the size powSetSize of the power set using the bitwise shift left operator (shl) to raise 2 to the power of n.
  4. Initialize an empty mutable list powerSet to hold the resulting power set.
  5. Loop through all possible binary numbers from 0 to 2^n – 1 using a for loop with the index variable i.
  6. Initialize an empty mutable set subset to hold the current subset being generated.
  7. Loop through each element in the input set using another for loop with the index variable j.
  8. Check if the jth bit in i is set using a bitwise AND operation (and) and the left shift operator shl.
  9. If the jth bit in i is set, add the corresponding element set[j] to the current subset using the add method of the MutableSet interface.
  10. After looping through all elements in the input set, add the current subset to the power set using the add method of the MutableList interface.
  11. Once all possible subsets have been generated and added to the power set, return the power set.
Kotlin
fun powerSet(set: IntArray): List<Set<Int>> {
    val n = set.size
    val powSetSize = 1 shl n
    val powerSet = mutableListOf<Set<Int>>()

    for (i in 0 until powSetSize) {
        val subset = mutableSetOf<Int>()
        for (j in 0 until n) {
            if (i and (1 shl j) != 0) {
                subset.add(set[j])
            }
        }
        powerSet.add(subset)
    }

    return powerSet
}
fun main() {
    val set = intArrayOf(1, 2, 3)
    val powerSet = powerSet(set)
    for (subset in powerSet) {
        println(subset)
    }
}

In this example, we create an integer array set containing the elements 1, 2, and 3, and pass it as an argument to the powerSet function. The resulting power set is then printed using a for loop to iterate over each subset in the list.

The output of running this main function would be:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

This represents the power set of the original set {1, 2, 3}, which includes all possible subsets including the empty set and the set itself.

Leave a Comment