[Haskell-beginners] Re: Majority Element

[Daniel Fischer]

Am Sonntag, 22. Februar 2009 17:12 schrieb Keith Sheppard:
> > Message: 8
> > Date: Sun, 22 Feb 2009 01:15:30 +0000
> > From: "Matthew J. Williams" <matthewjwilliams1 at googlemail.com>
> > Subject: [Haskell-beginners] Majority Element
> > To: beginners at haskell.org
> > Message-ID: <49a0a726.278e420a.6b19.ffffe361 at mx.google.com>
> > Content-Type: text/plain; charset="us-ascii"; format=flowed
> >
> > Dear listers
> >
> >        What is a majority element in an array?
> >
> >        Sincerely
> >        Matthew J. Williams
> >

The answer is implicit in Keith's code below, but let's state it also in plain 
text:

A majority element in a collection C of n things is a value that appears 
strictly more than n/2 times in C.

In general, no majority element exists.

I had never met the term before Matthew's post. Does anybody know for what it 
is important?

> I think this gets you what you want:
>
> majority nums = find (\x -> fromIntegral (length x) > (fromIntegral
> (length nums)) / 2) (group(sort(nums)))

You don't need the fromIntegral here, integer division does the right thing.
In case a majority element a exists, this returns Just [a,a...], so you might 
add an "fmap head" to get the element itself.

>
> It returns a "Maybe" list containing all majority elements. Something
> that avoids the sort would be faster though.

Not the naive algorithm. However, if the type of elements doesn't belong to 
Ord, we can't use sort :(

>
> -Keith
>

findMajority :: Eq a => [a] -> Maybe a
findMajority [] = Nothing
findMajority xxs@(x:xs) = case sweep x 1 xs of
                            Nothing -> Nothing
                            Just candidate -> verify candidate 0 xxs
      where
        sweep a count []
            | count == 0 = Nothing
            | otherwise = Just a
        sweep _ 0 (y:ys) = sweep y 1 ys
        sweep a count (y:ys)
            | a == y   = sweep a (count+1) ys
            | otherwise = sweep a (count-1) ys
        verify c count (y:ys)
            | c == y    = verify c (count+1) ys
            | otherwise = verify c (count-1) ys
        verify c count []
            | count > 0 = Just c
            | otherwise = Nothing

Cheers,
Daniel