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:

 1import Data.Bits
 2
 3lowest_set_bit :: Int -> Int
 4lowest_set_bit x = x .&. complement (x - 1)
 5
 6lowest_set_bit_index :: Int -> Int
 7lowest_set_bit_index x = floor (logBase (fromIntegral 2) (fromIntegral (lowest_set_bit x)))
 8
 9set_bit_positions :: Int -> [Int]
10set_bit_positions 0 = []
11set_bit_positions x = (lowest_set_bit_index x) : (set_bit_positions (clear_lowest_set_bit x))
12
13power_set :: [Char] -> [[Char]]
14power_set [] = []
15power_set alphabet = [str_from_int x | x <- [0 .. ((1::Int) `shiftL` numAlpha) - 1]]
16  where
17    numAlpha = length alphabet
18    str_from_int x = [alphabet !! i | i <- set_bit_positions x]