12

How to find the majority votes for a list that can contain -1s, 1s and 0s?

For example, given a list of:

x = [-1, -1, -1, -1, 0]

The majority is -1 , so the output should return -1

Another example, given a list of:

x = [1, 1, 1, 0, 0, -1]

The majority vote would be 1

And when we have a tie, the majority vote should return 0, e.g.:

x = [1, 1, 1, -1, -1, -1]

This should also return zero:

x = [1, 1, 0, 0, -1, -1]

The simplest case to get the majority vote seem to sum the list up and check whether it's negative, positive or 0. 

>>> x = [-1, -1, -1, -1, 0]
>>> sum(x) # So majority -> 0
-4
>>> x = [-1, 1, 1, 1, 0]
>>> sum(x) # So majority -> 1
2
>>> x = [-1, -1, 1, 1, 0]
>>> sum(x) # So majority is tied, i.e. -> 0
0

After the sum, I could do this check to get the majority vote, i.e.:

>>> x = [-1, 1, 1, 1, 0]
>>> majority = -1 if sum(x) < 0 else 1 if sum(x)!=0 else 0
>>> majority
1
>>> x = [-1, -1, 1, 1, 0]
>>> majority = -1 if sum(x) < 0 else 1 if sum(x)!=0 else 0
>>> majority
0

But as noted previously, it's ugly: Python putting an if-elif-else statement on one line and not pythonic.

So the solution seems to be 

>>> x = [-1, -1, 1, 1, 0]
>>> if sum(x) == 0:
...     majority = 0
... else:
...     majority = -1 if sum(x) < 0 else 1
... 
>>> majority
0

EDITED

But there are cases that sum() won't work, @RobertB's e.g. 

>>> x = [-1, -1, 0, 0, 0, 0]
>>> sum(x) 
-2

But in this case the majority vote should be 0!!

Community
  • 1
  • 1
alvas
  • 115,346
  • 109
  • 446
  • 738

13 Answers13

15

I am assuming that votes for 0 count as votes. So sum is not a reasonable option.

Try a Counter:

>>> from collections import Counter
>>> x = Counter([-1,-1,-1, 1,1,1,1,0,0,0,0,0,0,0,0])
>>> x
Counter({0: 8, 1: 4, -1: 3})
>>> x.most_common(1)
[(0, 8)]
>>> x.most_common(1)[0][0]
0

So you could write code like:

from collections import Counter

def find_majority(votes):
    vote_count = Counter(votes)
    top_two = vote_count.most_common(2)
    if len(top_two)>1 and top_two[0][1] == top_two[1][1]:
        # It is a tie
        return 0
    return top_two[0][0]

>>> find_majority([1,1,-1,-1,0]) # It is a tie
0
>>> find_majority([1,1,1,1, -1,-1,-1,0])
1
>>> find_majority([-1,-1,0,0,0]) # Votes for zero win
0
>>> find_majority(['a','a','b',]) # Totally not asked for, but would work
'a'
RobertB
  • 1,879
  • 10
  • 17
12

You could use statistics.mode if you were using python >= 3.4 ,catching a StatisticsError for when you have no unique mode:

from statistics import mode, StatisticsError

def majority(l):
    try:
        return mode(l)
    except StatisticsError:
        return 0

The statistics implementation itself uses a Counter dict:

import  collections
def _counts(data):
    # Generate a table of sorted (value, frequency) pairs.
    table = collections.Counter(iter(data)).most_common()
    if not table:
        return table
    # Extract the values with the highest frequency.
    maxfreq = table[0][1]
    for i in range(1, len(table)):
        if table[i][1] != maxfreq:
            table = table[:i]
            break
    return table

def mode(data):
    """Return the most common data point from discrete or nominal data.

    ``mode`` assumes discrete data, and returns a single value. This is the
    standard treatment of the mode as commonly taught in schools:

    >>> mode([1, 1, 2, 3, 3, 3, 3, 4])
    3

    This also works with nominal (non-numeric) data:

    >>> mode(["red", "blue", "blue", "red", "green", "red", "red"])
    'red'

    If there is not exactly one most common value, ``mode`` will raise
    StatisticsError.
    """
    # Generate a table of sorted (value, frequency) pairs.
    table = _counts(data)
    if len(table) == 1:
        return table[0][0]
    elif table:
        raise StatisticsError(
                'no unique mode; found %d equally common values' % len(table)
                )
    else:
        raise StatisticsError('no mode for empty data')

Another way using a Counter and catching an empty list:

def majority(l):
    cn = Counter(l).most_common(2)
    return 0 if len(cn) > 1 and cn[0][1] == cn[1][1] else next(iter(cn),[0])[0]
Padraic Cunningham
  • 176,452
  • 29
  • 245
  • 321
1

You can count occurences of 0 and test if they are majority. 

>>> x = [1, 1, 0, 0, 0]
>>> if sum(x) == 0 or x.count(0) >= len(x) / 2.0:
...     majority = 0
... else:
...     majority = -1 if (sum(x) < 0) else 1
... majority
0
Community
  • 1
  • 1
Szymon Zmilczak
  • 353
  • 3
  • 11
1

This solution is based on counting occurrences and sorting:

import operator
def determineMajority(x):
    '''
    >>> determineMajority([-1, -1, -1, -1, 0])
    -1

    >>> determineMajority([1, 1, 1, 0, 0, -1])
    1

    >>> determineMajority([1, 1, 1, -1, -1, -1])
    0

    >>> determineMajority([1, 1, 1, 0, 0, 0])
    0

    >>> determineMajority([1, 1, 0, 0, -1, -1])
    0

    >>> determineMajority([-1, -1, 0, 0, 0, 0])
    0
    '''

    # Count three times
    # sort on counts
    xs = sorted(
        [(i, x.count(i)) for i in range(-1,2)],
        key=operator.itemgetter(1),
        reverse=True
    )

    if xs[0][1] > xs[1][1]:
        return xs[0][0]
    else:
        # tie
        return 0


if __name__ == '__main__':
    import doctest
    doctest.testmod()

Additionally, there is one if statements. As mentioned in the comments it is undefined what happens with

x = [1, 1, 0, 0, -1]

crlb
  • 1,282
  • 12
  • 18
1
# These are your actual votes
votes = [-1, -1, -1, -1, 0]

# These are the options on the ballot
ballot = (-1, 0, 1)

# This is to initialize your counters
counters = {x: 0 for x in ballot}

# Count the number of votes
for vote in votes:
    counters[vote] += 1

results = counters.values().sort()

if len(set(values)) < len(ballot) and values[-1] == values [-2]:
    # Return 0 if there's a tie
    return 0
else:
    # Return your winning vote if there isn't a tie
    return max(counters, key=counters.get)
veggie1
  • 717
  • 3
  • 12
1

A very simple approach.

a = [-1, -1, -1, -1, 0]   # Example
count = {}
for i in a:
    if i not in count:
        count[i] = 1
    else:
        count[i] += 1
m_count = max(count.values())
for key in count:
    if count[key] == m_count:
        print key

In the above example the output will be -1, however if there is a tie, both the keys will be printed.

Amitkumar Karnik
  • 912
  • 13
  • 23
0
from collections import Counter

result = Counter(votes).most_common(2)

result = 0 if result[0][1] == result[1][1] else result[0][0]

Error handling for empty votes lists or votes lists with a set cardinality of 1 is trivial and left as an exercise for the reader.

Garry Cairns
  • 3,005
  • 1
  • 18
  • 33
0

I believe this works for all provided test cases. Please let me know if I did something wrong.

from collections import Counter

def fn(x):
    counts = Counter(x)
    num_n1 = counts.get(-1, 0)
    num_p1 = counts.get(1, 0)
    num_z = counts.get(0, 0)
    if num_n1 > num_p1:
        return -1 if num_n1 > num_z else 0
    elif num_p1 > num_n1:
        return 1 if num_p1 > num_z else 0
    else:
        return 0
Shashank
  • 13,713
  • 5
  • 37
  • 63
  • Why are you doing tests to mc? In every case you can just return mc. – RobertB Nov 04 '15 at 00:35
  • @RobertB Yes I realize that. Sorry I will fix it. – Shashank Nov 04 '15 at 00:36
  • Ok now I like it. It is more compact than mine ;) – RobertB Nov 04 '15 at 00:37
  • Question: If you have an input of `[0,0,0,1,1,1]` or `[-1, -1, -1, 0,0,0]`, these are ties. Will `most_common(1)[0][0]` always return 0? Might it sometimes return 1? Can't find any documentation on this, so I worry. In practice, it seems to consistently return 0, but I'm not sure why. – RobertB Nov 04 '15 at 01:23
  • @RobertB You have made me realize that my answer is undefined for those test cases. In [the documentation](https://docs.python.org/3/library/collections.html#collections.Counter.most_common) it clearly states that there is no guarantee over the order of returned elements from Counter.most_common. Makes sense because the underlying structure is typically a dictionary which is ordered in a volatile hash table bucket scheme. However, it should be noted that the question itself did not define what should happen in these "tie" cases between 1 or -1 and 0. – Shashank Nov 04 '15 at 02:47
  • But it does. Ties are supposed to be 0 – RobertB Nov 04 '15 at 05:07
  • @Robert Ok, in that case, my old answer was wrong. I've updated the code so that it works correctly for all test cases. It is no longer a succinct one-liner, but the code is at least efficient and easy to understand. – Shashank Nov 04 '15 at 12:36
0

This works with any number of candidates. If there is a tie between two candidates it returns zero else it returns candidate with most votes.

from collections import Counter
x = [-1, -1, 0, 0, 0, 0]
counts = list((Counter(x).most_common())) ## Array in descending order by votes
if len(counts)>1 and (counts[0][1] == counts[1][1]): ## Comparing top two candidates 
   print 0
else:
   print counts[0][0]

We compare only two candidates because if there is a tie between two candidates it should return 0 and it doesn't depend on third candidate value

David Zwicker
  • 23,581
  • 6
  • 62
  • 77
Harwee
  • 1,601
  • 2
  • 21
  • 35
  • okay you can ignore my answer. I gave the same answer as RobertB . I checked it after answering the question. – Harwee Nov 11 '15 at 23:42
0

An obvious approach is making a counter and updating it according to the data list x. Then you can get the list of numbers (from -1, 0, 1) that are the most frequent. If there is 1 such number, this is what you want, otherwise choose 0 (as you requested).

counter = {-1: 0, 0: 0, 1: 0}
for number in x:
    counter[number] += 1
best_values = [i for i in (-1, 0, 1) if counter[i] == max(counter.values())]
if len(best_values) == 1:
    majority = best_values[0]
else:
    majority = 0
dorverbin
  • 467
  • 1
  • 4
  • 17
-1

You don't need anything but built-in list operators and stuff, no need to import anything.

  votes = [ -1,-1,0,1,0,1,-1,-1] # note that we don't care about ordering

    counts = [ votes.count(-1),votes.count(0),votes.count(1)] 

    if (counts[0]>0 and counts.count(counts[0]) > 1) or (counts[1]>0 and counts.count(counts[1])>1):
         majority=0
    else:
         majority=counts.index(max(counts))-1 # subtract 1 as indexes start with 0

    print majority

3d line puts counts of respective votes in a new list, and counts.index() shows us which list position we find the max votes.

I would dare to say that this should be about as pythonic as it can, without getting into eye-gouging oneliners.

Upd: rewrote without text strings and updated to return 0 in case of several equal results (didnt notice this in the original post), added an IF for case if only one vote, eg votes=[-1]

Gnudiff
  • 4,297
  • 1
  • 24
  • 25
-1
from collections import Counter

def find_majority_vote(votes):
  counter = Counter(votes)
  most_common = counter.most_common(2)
  if len(most_common)==2:
    return 0 if most_common[0][1] == most_common[1][1] else most_common[0][0]
  else:
    return most_common[0][0]
gipsy
  • 3,859
  • 1
  • 13
  • 21
-2
import numpy as np

def fn(vote):
   n=vote[np.where(vote<0)].size
   p=vote[np.where(vote>0)].size
   ret=np.sign(p-n)
   z=vote.size-p-n
   if z>=max(p,n):
      ret=0
   return ret

# some test cases
print fn(np.array([-1,-1, 1,1,1,1,0,0,0,0,0,0,0,0]))
print fn(np.array([-1, -1, -1, 1,1,1,0,0]))
print fn(np.array([0,0,0,1,1,1]))
print fn(np.array([1,1,1,1, -1,-1,-1,0]))
print fn(np.array([-1, -1, -1, -1, 1, 0]))
Felix Darvas
  • 507
  • 3
  • 5