Поиск большинства голосов на -1, 1 и 0 в списке - python

Как найти большинство голосов для списка, который может содержать -1, 1 и 0?

Например, при наличии списка:

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

Большинство равно -1 , поэтому вывод должен возвращать -1

Другой пример, учитывая список:

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

Большинство голосов будет 1

И когда у нас ничья, большинство голосов должно вернуть 0, например:

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

Это также должно возвращать ноль:

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

Самый простой случай получить большинство голосов, кажется, суммировать список и проверить, является ли он отрицательным, положительным или 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

После суммы я мог бы сделать эту проверку, чтобы получить большинство голосов, то есть:

>>> 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

Но, как отмечалось ранее, это уродливо: Python, помещающий -elif-else в одну строку, а не pythonic.

Так что решение похоже

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

ОТРЕДАКТИРОВАНО

Но есть случаи, когда sum() не работает, например, @RobertB.

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

Но в этом случае большинство голосов должно быть 0!!


person alvas    schedule 03.11.2015    source источник
comment
Может ли большинство голосов равняться 0? Итак, если [-1, -1, 0, 0, 0, 0] ответ равен нулю? В этом случае sum вам не подойдет.   -  person RobertB    schedule 04.11.2015
comment
Это не заявление; это выражение. Как использование одного из встроенных выражений в языке может быть не питоническим?   -  person saulspatz    schedule 04.11.2015
comment
ооо, да, верно. Итак, каково решение?   -  person alvas    schedule 04.11.2015
comment
Я бы порекомендовал вам заменить большинство на множественность в названии и определении вашей проблемы, поскольку, похоже, это то, что вы имеете в виду. Это довольно значительная разница в решении.   -  person gariepy    schedule 09.11.2015
comment
Всегда ли они сгруппированы?   -  person Padraic Cunningham    schedule 10.11.2015
comment
Неа. они не всегда сгруппированы, но сортировка естественным образом сгруппировала бы их =)   -  person alvas    schedule 10.11.2015
comment
А как насчет [1, 1, 0, 0]?   -  person Alex Hall    schedule 10.11.2015
comment
О, подождите, нет, если ничья, return 0 в OP.   -  person alvas    schedule 10.11.2015
comment
Я вижу награду, но я не уверен, что не так с ответом, который я дал.   -  person RobertB    schedule 10.11.2015
comment
@RobertB Просто хочу увидеть альтернативу других людей, чтобы решить эту проблему =)   -  person alvas    schedule 10.11.2015


Ответы (10)


Я предполагаю, что голоса за 0 считаются голосами. Так что sum не лучший вариант.

Попробуйте счетчик:

>>> 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

Таким образом, вы можете написать код, например:

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'
person RobertB    schedule 03.11.2015
comment
Что там ничья со счетчиком? например x = [1, 1, 0, 0, -1]? - person alvas; 04.11.2015
comment
В случае x = [1, 1, 0, 0, -1] большинство составляют оба 1 and 0. - person alvas; 04.11.2015
comment
Попытайся. В любом случае, счетчик упрощает все, что я думаю. - person RobertB; 04.11.2015
comment
Хорошо, я дал вам решение в ответе. - person RobertB; 04.11.2015

Вы можете использовать statistics.mode, если используете python >= 3.4, поймать StatisticsError, если у вас нет уникального режима:

from statistics import mode, StatisticsError

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

Сама реализация статистики использует 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')

Другой способ использования счетчика и получения пустого списка:

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]
person Padraic Cunningham    schedule 07.11.2015

Вы можете подсчитывать вхождения 0 и проверить, являются ли они большинством.

>>> 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
person Szymon Zmilczak    schedule 07.11.2015
comment
За исключением случаев, когда OP говорит о большинстве, это, по-видимому, означает множество. - person gariepy; 09.11.2015
comment
Попробуйте x = [1,-1,-1,0,0] - person Padraic Cunningham; 11.11.2015
comment
x = [1,-1,-1,0,0] даст majority = -1 - person Szymon Zmilczak; 13.11.2015

Это решение основано на подсчете вхождений и сортировке:

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()

Кроме того, есть один оператор if. Как упоминалось в комментариях, не определено, что происходит с

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

person hakanc    schedule 09.11.2015

Очень простой подход.

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

В приведенном выше примере вывод будет -1, однако, если есть ничья, будут напечатаны оба ключа.

person Amit Karnik    schedule 12.11.2015

Я считаю, что это работает для всех предоставленных тестовых случаев. Пожалуйста, дайте мне знать, если я сделал что-то не так.

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
person Shashank    schedule 04.11.2015
comment
Почему вы делаете тесты для mc? В любом случае вы можете просто вернуть mc. - person RobertB; 04.11.2015
comment
@RobertB Да, я понимаю это. Извините, я исправлю. - person Shashank; 04.11.2015
comment
Хорошо, теперь мне это нравится. Он компактнее моего ;) - person RobertB; 04.11.2015
comment
Вопрос: Если у вас есть вход [0,0,0,1,1,1] или [-1, -1, -1, 0,0,0], это ничья. Будет ли most_common(1)[0][0] всегда возвращать 0? Может ли он иногда возвращать 1? Не могу найти никакой документации по этому поводу, поэтому я беспокоюсь. На практике кажется, что он постоянно возвращает 0, но я не уверен, почему. - person RobertB; 04.11.2015
comment
@RobertB Вы заставили меня понять, что мой ответ не определен для этих тестовых случаев. В документации четко указано, что гарантировать порядок возвращаемых элементов из Counter.most_common. Это имеет смысл, потому что базовая структура обычно представляет собой словарь, который упорядочен по схеме сегмента энергозависимой хеш-таблицы. Однако следует отметить, что сам вопрос не определял, что должно происходить в этих случаях равенства между 1 или -1 и 0. - person Shashank; 04.11.2015
comment
Но это так. Ничья должна быть 0 - person RobertB; 04.11.2015
comment
@Robert Хорошо, в таком случае мой старый ответ был неправильным. Я обновил код, чтобы он работал правильно для всех тестовых случаев. Это уже не краткий однострочный код, но код по крайней мере эффективен и прост для понимания. - person Shashank; 04.11.2015

from collections import Counter

result = Counter(votes).most_common(2)

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

Обработка ошибок для пустых списков votes или списков votes с установленным числом элементов, равным 1, тривиальна и оставлена ​​читателю в качестве упражнения.

person Garry Cairns    schedule 04.11.2015
comment
Вау. Я никогда не использовал max таким образом... это очень умно. - person RobertB; 04.11.2015
comment
Я не думаю, что это даст вам то, что вы хотите, если голоса, например. [-1, -1, 1, 1] - person Tom Karzes; 04.11.2015
comment
@TomKarzesThat дает 0, поскольку sum([-1,-1,1,1]) равно 0, что правильно, поскольку это ничья, учитывая правила. Что, по вашему мнению, было не так? - person RobertB; 04.11.2015
comment
О, ладно, извините - я этого не заметил. Каким должен быть результат, если голосов [-1, 0, 0, 0, 1, 1]? Разве вы не хотите 1 в таком случае? - person Tom Karzes; 04.11.2015
comment
0, так как нулей больше, чем любых других. - person RobertB; 04.11.2015
comment
Хорошо, подождите, а что, если голосов будет: [-1, 0, 0, 1, 1]? В отличие от [-1, 1, 1, 0, 0]? Они дают разные ответы. - person Tom Karzes; 04.11.2015
comment
@TomKarzes, пожалуйста, посмотрите мое обновление, в котором учтено то, что вы заметили. - person Garry Cairns; 04.11.2015
comment
Ваше новое изменение не будет выполнено, если все проголосуют одинаково [1,1,1] - person RobertB; 04.11.2015

Это работает с любым количеством кандидатов. Если между двумя кандидатами есть ничья, возвращается ноль, в противном случае возвращается кандидат с наибольшим количеством голосов.

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]

Мы сравниваем только двух кандидатов, потому что, если между двумя кандидатами есть ничья, он должен вернуть 0, и это не зависит от значения третьего кандидата.

person Harwee    schedule 11.11.2015
comment
хорошо, вы можете игнорировать мой ответ. Я дал тот же ответ, что и RobertB. Я проверил это после ответа на вопрос. - person Harwee; 12.11.2015

Очевидным подходом является создание счетчика и его обновление в соответствии со списком данных x. Затем вы можете получить список чисел (от -1, 0, 1), которые встречаются чаще всего. Если есть 1 такое число, это то, что вам нужно, в противном случае выберите 0 (как вы просили).

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
person dorverbin    schedule 12.11.2015

Вам не нужно ничего, кроме встроенных операторов списков и прочего, не нужно ничего импортировать.

  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

3-я строка помещает количество соответствующих голосов в новый список, а counts.index() показывает нам, в какой позиции списка мы находим максимальное количество голосов.

Я бы осмелился сказать, что это должно быть настолько питоническим, насколько это возможно, не вдаваясь в выдавливающие глаза остроты.

Upd: переписано без текстовых строк и обновлено, чтобы возвращать 0 в случае нескольких одинаковых результатов (не заметил этого в исходном посте), добавлен IF для случая, если только один голос, например, voices=[-1]

person Gnudiff    schedule 09.11.2015