Majority Element

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Majority Element

Matthew J. Williams
Dear listers

        What is a majority element in an array?

        Sincerely
        Matthew J. Williams

Reply | Threaded
Open this post in threaded view
|

Majority Element

Andrew Wagner
I've never heard this term. Can you give some context?

On Sat, Feb 21, 2009 at 8:15 PM, Matthew J. Williams <
[hidden email]> wrote:

> Dear listers
>
>        What is a majority element in an array?
>
>        Sincerely
>        Matthew J. Williams
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090221/ef1e1c3d/attachment.htm
Reply | Threaded
Open this post in threaded view
|

Re: Majority Element

Keith Sheppard
In reply to this post by Matthew J. Williams
I think this gets you what you want:

majority nums = find (\x -> fromIntegral (length x) > (fromIntegral
(length nums)) / 2) (group(sort(nums)))

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

-Keith

> Message: 8
> Date: Sun, 22 Feb 2009 01:15:30 +0000
> From: "Matthew J. Williams" <[hidden email]>
> Subject: [Haskell-beginners] Majority Element
> To: [hidden email]
> Message-ID: <[hidden email]>
> Content-Type: text/plain; charset="us-ascii"; format=flowed
>
> Dear listers
>
>        What is a majority element in an array?
>
>        Sincerely
>        Matthew J. Williams
>
>
>
> ------------------------------
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
Reply | Threaded
Open this post in threaded view
|

Re: Majority Element

Daniel Fischer-4
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" <[hidden email]>
> > Subject: [Haskell-beginners] Majority Element
> > To: [hidden email]
> > Message-ID: <[hidden email]>
> > 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