Langford pairs in Haskell

 

\This implementation is not-very naive but it is not very efficient either. It can generate solutions up to n = 12, then it gets very slow.

This is an extremely horrible solution to generate langford pairs by
dilawar@ee.iitb.ac.in succesfully finished on Nov 27, 2011 after two days of
labour. Is is advised not to use this program in any real-time application. Its
runs slower than Chacha Chaudary brain.

One can achieve much better performace by using Arrays in Haskell.

This is discussed in Knuth, TAOP - Vol 4(a)

> mkZero n = take n [0,0..]

> genBaseList n
>     | n < 1 = [] >     | otherwise = n : mkZero n ++ [n]

We are producing baselists e.g. for n=4, baselists are [1,0,1], [2,0,0,2],
[3,0,0,0,3] and [4,0,0,0,0,4].

> allBaseLists n = map genBaseList [n,n-1..1]

Following horrible step is the core of our algorithm. In this step we use two
base-list. First list is known as topList while the other one is bottomList. To
fuse these lists, we first shift the top-list to right by prepending a 0 to it
and fuse it with bottom. Two lists are no fusable whenver both of them has
non-zero integer at the same place. This process stops when size of top list
become more than 2*n we stop. For example, for n = 3

Top   : 1 0 1    | 0 1 0 1 | 0 0 1 0 1 | 0 0 0 1 0 1 | size more than 2n
Bot   : 2 0 0 2  | 2 0 0 2 | 2 0 0 2   | 2 0 0 2

Fuse  : X        | 2 1 0 X | 2 0 1 2 1 | 2 0 0 X
Nothing    Nothing     Just       Nothing
^                        ^
|                        |
Two nozero             This is the only
Entries coincide       possible fusion.

In second step, we shift the bottom and fuse
Top   : 1 0 1    | 1 0 1      | 1 0 1         | 1 0 1
Bot   : 2 0 0 2  | 0 2 0 0 2  | 0 0 2 0 0 2   | size more than 2n

Fuse  : X        | 1 2 1 0 2  | 1 0 X
Nothing      Just        Nothing

> fuseBothList [] y = Just y
> fuseBothList x [] = Just x
> fuseBothList (x:xs) (y:ys)
>     | (x /= 0) && (y /= 0) = Nothing
>     | otherwise = (helper $ fuseBothList xs ys)
>                         where helper Nothing = Nothing
>                               helper (Just p) = if y/=0 then Just (y:p)
>                                                 else Just (x:p)
>
> topRightShiftAndFuse t b n
>     | length (t) > 2*n = []
>     | fuseBothList t b == Nothing = topRightShiftAndFuse (0:t) b n
>     | otherwise = (\(Just p) -> p:(topRightShiftAndFuse (0:t) b n)) (fuseBothList t b)
>
>
> botRightShiftAndFuse t b n
>     | length (b) > 2*n = []
>     | fuseBothList t b == Nothing = botRightShiftAndFuse t (0:b) n
>     | otherwise = (\(Just p) -> p:(botRightShiftAndFuse t (0:b) n)) (fuseBothList t b)
>
>

At each step we get fused lists by above method. These lists are needed to be
fused with next list And now we should merge what we have fused. For example we
have got [0,2,0,0,2] and [1,2,1,0,2] from previous merge, now we need to merge
it with [3,0,0,0,3]. by doing so, we'll get the solution for n=3.

> mergeTopBottom t b n = (topRightShiftAndFuse t b n) ++ (botRightShiftAndFuse t b n)

Now rest is putting these function together to get the final solution.

> initList n = allBaseLists n
> mergeInto n = (\(x:xs) -> mergeTopBottom (head xs) x n) (initList n)
> mergeFrom n = (\(x:y:zs) -> zs) (initList n)

This is my ultimate answer.
generateSol mergeFromList mergeIntoList n. It generates duplicate solution.

> generateSol (b:[]) a n
>     = foldr (++) [] $ map (\x -> mergeTopBottom b x n) a
> generateSol (b:bs) (a) n
>     = generateSol bs (foldr (++) [] (map (\x -> mergeTopBottom b x n) a)) n

And now I should combile all of them to write the top-most function.

> langfordPair n = generateSol (mergeFrom n) (mergeInto n) n
> totalPairs n = length (langfordPair n)

Who needs tests now!
test1 = mergeTopBottom [2,0,0,2] [3,0,0,0,3] 3
test2 = map (\x -> mergeTopBottom [1,0,1] x 3) test1
test4 = mergeThisList [2,0,0,2]
test5 = mergeThisList
Advertisements

About Dilawar

Graduate Student at National Center for Biological Sciences, Bangalore.
This entry was posted in Algorithms, Haskell, Programming and tagged , . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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