Posts Tagged ‘repeated’

Programming Praxis – Stepwise Program Development: A Heuristic Algorithm

December 11, 2012

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