Power set: bitwise vs recursion

  So, I’ve already written that bitwise operations is a very fast thing. But how can this be used in application ? Let’s say, you need to iterate over the powerset of some elements which can be useful in various fields(for example):

• operations with graphs;
• dynamic programming problems, where all combinations of elements should be stored in memoization table;
• other combinatorial problems…

  There are two approaches for generating powerset: recursion and bitwise operations. Which of them performs better? Let’s test.

class PowerSet(
val set: IntArray,
) {
val subSets = mutableListOf<IntArray>()

    fun generateRecursive(at: Int, used: BooleanArray) {
        val n = set.size;
        val range = set.indices
        if (at == n) {

            // Print found subset!
            var subSet = IntArray(n)
            for (i in range) {
                if (used[i]) {
                    subSet[i] = set[i]
                }
            }
            subSets.add(subSet)
        } else {

            // Include this element
            used[at] = true
            generateRecursive(at + 1, used)

            // Backtrack and don't include this element
            used[at] = false
            generateRecursive(at + 1, used)
        }
    }

    fun generateBinary() {
        val n = set.size;
        val range = set.indices
        val maxVal = 1 shl n;

        for (subset in 0 until maxVal) {
            var subSet = IntArray(n)
            for (i in range) {
                val mask = 1 shl i
                if ((subset and mask) == mask) {
                    subSet[i] = set[i]
                }
            }
            subSets.add(subSet)
        }
    }

}
  

@State(Scope.Benchmark)
class PowerSetBenchmark {
@Param("3", "4", "5", "10", "20", "26")
var setSize = 0
lateinit var set: IntArray

    @Setup
    fun setUp() {
        set = IntArray(setSize) { i -> i }
    }


    @Benchmark
    fun powSetRecursive() {
        val ps = PowerSet(set)
        ps.generateRecursive(
            0, BooleanArray(setSize)
        )

    }

    @Benchmark
    fun powSetBinary() {
        val ps = PowerSet(set)
        ps.generateBinary()
    }

}

Source code of PowerSet class and benchmark

Results

Benchmark                          (setSize)  Mode  Cnt        Score         Error  Units
PowerSetBenchmark.powSetBinary             3  avgt    3        0.060 ±       0.065  us/op
PowerSetBenchmark.powSetBinary             4  avgt    3        0.137 ±       0.046  us/op
PowerSetBenchmark.powSetBinary             5  avgt    3        0.286 ±       0.064  us/op
PowerSetBenchmark.powSetBinary             9  avgt    3        6.654 ±       6.681  us/op
PowerSetBenchmark.powSetBinary            10  avgt    3       14.016 ±      18.000  us/op
PowerSetBenchmark.powSetBinary            11  avgt    3       82.002 ±      63.015  us/op
PowerSetBenchmark.powSetBinary            20  avgt    3    92927.224 ±   28005.295  us/op
PowerSetBenchmark.powSetBinary            26  avgt    3  8389329.133 ± 2665432.289  us/op
PowerSetBenchmark.powSetRecursive          3  avgt    3        0.076 ±       0.017  us/op
PowerSetBenchmark.powSetRecursive          4  avgt    3        0.191 ±       0.087  us/op
PowerSetBenchmark.powSetRecursive          5  avgt    3        0.400 ±       0.071  us/op
PowerSetBenchmark.powSetRecursive          9  avgt    3        7.283 ±       0.500  us/op
PowerSetBenchmark.powSetRecursive         10  avgt    3       20.408 ±      33.346  us/op
PowerSetBenchmark.powSetRecursive         11  avgt    3       57.855 ±      15.787  us/op
PowerSetBenchmark.powSetRecursive         20  avgt    3    82136.368 ±   75290.816  us/op
PowerSetBenchmark.powSetRecursive         26  avgt    3  7995903.683 ± 2029323.013  us/op

  As you can notice from benchmark summary binary implementation is faster with n <= 10, but with n=11 recursive implementation becomes faster.
  For me its pretty unexpected result which I cannot explain at the moment. So much the better, another interesting topic to explore is put to the piggy-bank :-) See you!