Programming Praxis – Stepwise Program Development: A Heuristic Algorithm

In today’s exercise, our goal is to write an algorithm that, given an alphabet and a length, generates all possible sequences that do not have two adjacent indentical subsequences. Let’s get started, shall we?

Some imports:

import Control.Monad
import Data.List

We build up the list of possible sequences from the end. Whenever we add a character we check that we do not generate a repeated subsequence. This bit could be optimised a little since checking past the first half of the list is pointless, but performance wasn’t a problem so I didn’t bother. Although not explicitly stated in the problem description, two sequences are considered identical if one can be obtained by permuting the other’s alphabet, e.g. 123 is considered the same thing as 321. Therefor we add the criterium that in the final list of permutations all unique characters must occur in ascending order.

nonAdjacent :: Ord a => [a] -> Int -> [[a]]
nonAdjacent xs = sort . filter (and . zipWith (==) xs . nub) . f where
    f 0 = [[]]
    f n = filter (\x -> not . or . tail $ zipWith isPrefixOf (inits x) (tails x)) $
          liftM2 (:) xs (f $ n - 1)

Some tests to see if everything is working properly:

main :: IO ()
main = do mapM_ putStrLn $ nonAdjacent "123" 5
          mapM_ putStrLn $ nonAdjacent "123" 12
          mapM_ putStrLn $ nonAdjacent "123" 20
About these ads

Tags: , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: