# Re: Factor

Factor: the language, the theory, and the practice.

## Majority Vote

Saturday, July 23, 2011

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?