Re: Factor

A Linear Time Majority Vote Algorithm was invented in 1980 by Bob Boyer and J Strother Moore (inventors of the popular Boyer-Moore string search algorithm). Not seeing this available in Factor, I thought to contribute one.

Note: this is also called the “Moore’s Voting Algorithm”.

The algorithm simply looks at each element of the sequence:

Keep a candidate element and a counter (initially unknown and zero, respectively).

As we move across the sequence, look at each element:

• If the counter is 0: the element is the candidate and the counter is 1.
• If the counter is not 0: increment if the element is the candidate, decrement if not.

When we are done, the candidate is the majority element, if there is a majority.

Using this specification, we can implement the algorithm:

: majority ( seq -- elt/f )
    [ f 0 ] dip [
        over zero? [ 2nip 1 ] [ 
            pick = [ 1 + ] [ 1 - ] if
        ] if
    ] each zero? [ drop f ] when ;

A few simple tests show that this is working:

{ f } [ { } majority ] unit-test
{ f } [ { 1 2 } majority ] unit-test
{ 1 } [ { 1 1 2 } majority ] unit-test
{ f } [ { 1 1 2 2 } majority ] unit-test
{ 2 } [ { 1 1 2 2 2 } majority ] unit-test

This is perhaps not quite idiomatic Factor, can you improve it?