EPI 6.1 Dutch Flag Partition

Problem:

Write a function that taks an Array A and an index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed by elements equal to A[i], followed by elements greater than A[i].

Solution:

First we define a couple of auxiliary helper functions to create haskell Arrays from haskell lists and a method to swap elements at two indexes in an Array:

import Data.Array

arrayFromList input startIndex = array bounds [(i + startIndex, x) | (i,x) <- (zip indexes input)]
            where
                bounds = (startIndex, startIndex + (length input) - 1)
                indexes = [0 .. length input]

swapItems xs a b = xs // [(b, xa)] // [(a, xb)]
            where
                xa = xs!a
                xb = xs!b

Now the algorithm. The core of the algorithm is to start with 4 partitions (with in the original Array):

smaller – All items smaller than the pivot element (originally A[i])
equal – All items equal to the pivot item
larger – All items larger than the pivot item
unclassified – Items that have not yet been classified into one of the above arrays.

Intuitively #unclassified = |A| – #smaller + #equal + #larger and this will become 0 at the end.

Initially #smaller, #equal and #larger = 0, 0 and |A| – 1 respectively. The following tail recursive solution updates one or more of these regions in each step as it iterates through the array (and stopping when the “equal” region “hits” the “larger” region).


dutch_flag_partition xs i = elems (dutch_flag_partition' arrayXS i 0 0 ((length xs) - 1))
    where
        arrayXS = (arrayFromList xs 0)
        pivot = arrayXS ! i
        dutch_flag_partition' xs i s e l
            | e > l = xs
            | (xs!e) < pivot = dutch_flag_partition' (swapItems xs s e) i (s + 1) (e + 1) l
            | (xs!e) == pivot = dutch_flag_partition' xs i s (e + 1) l
            | otherwise = dutch_flag_partition' (swapItems xs e l) i s e (l - 1)

A quick note. In this example (and others) we are using immutable collections. From an efficiency point of view using mutable collections would result in, well more efficiency. However we are striving for a balance between efficiency and reasonably simple code that is close enough to the guaranteed algorithmic complexities when these subtle differences (such as immutable vs mutable) are ignored.

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]