EPI 5.5 – Generating Power Sets

Problem:

The power set of an alphabet set, S is the list of all strings (of any lengths) that can be formed from the symbols in S.  There can be no repetitions however with respect to character swaps within the string.

For instance, for S = “ABC”, one possible power set is:

“”, “A”, “B”, “C”, “AB”, “AC”, “BC”, “ABC”

Solution:

The simplest way to think about this as iterating through the numbers 0 to 2^|S|, where each bit in the integer represents whether the alphabet at that index in the set, S is present in the output.  So a solution for this is:


import Data.Bits

lowest_set_bit :: Int -> Int
lowest_set_bit x = x .&. complement (x - 1)

lowest_set_bit_index :: Int -> Int
lowest_set_bit_index x = floor (logBase (fromIntegral 2) (fromIntegral (lowest_set_bit x)))

set_bit_positions :: Int -> [Int]
set_bit_positions 0 = []
set_bit_positions x = (lowest_set_bit_index x) : (set_bit_positions (clear_lowest_set_bit x))

power_set :: [Char] -> [[Char]]
power_set [] = []
power_set alphabet = [str_from_int x | x <- [0 .. ((1::Int) `shiftL` numAlpha) - 1]]
  where 
    numAlpha = length alphabet
    str_from_int x = [alphabet !! i | i <- set_bit_positions x]

EPI 5.1: Find the number of bits set in a number (and Parity)

The goal is to find the number of set bits in a number, when converted to binary.

So 4 (dec) -> 100 (bin)  –  has 1 bit set.

Similarly 7 -> 111 -> 3

The straightforward solution shown below has complexity of O(n) where n is the length of the input ie 8 bits for char, 16 bits for short, and 32 bits for int (ignoring hardware and compiler specific sizes here).

import Data.Bits

num_set_bits_simple 0 = 0
num_set_bits_simple x = case x .&. 1 of
                          1 -> 1 + num_set_bits_simple (x `shiftR` 1)
                          0 -> num_set_bits_simple (x `shiftR` 1)

Apart from being O(n) this also has the disadvantage of not being tail-call recursive and requires a conditional check in each “iteration”.

A solution that depends is O(s) where is the number of set bits is:

num_set_bits 0 = 0
num_set_bits x = 1 + num_set_bits (clear_lowest_set_bit x)

where

clear_lowest_set_bit x = x .&. (x - 1)

Here x & (x – 1) clears the lowest set bit in a number!