Какой самый питонный способ гарантировать, что все элементы списка различны?

Question

У меня есть список на Python, который я генерирую как часть программы. У меня есть сильное предположение, что все они разные, и я проверяю это утверждением.

Вот как я это делаю сейчас:

Если есть два элемента:

try:
    assert(x[0] != x[1])
except:
    print debug_info
    raise Exception("throw to caller")

Если их три:

try:
    assert(x[0] != x[1])
    assert(x[0] != x[2])
    assert(x[1] != x[2])
except:
    print debug_info
    raise Exception("throw to caller")

И если мне когда-нибудь придется сделать это с четырьмя элементами, я сойду с ума.

Есть ли лучший способ убедиться, что все элементы списка уникальны?

Answer 1

Может быть, что-то вроде этого:

if len(x) == len(set(x)):
    print "all elements are unique"
else:
    print "elements are not unique"

Answer 2

Самые популярные ответы - O (N) (хорошо! -), но, как указывают @Paul и @Mark, они требуют, чтобы элементы списка были хэшируемыми. Предложенные @Paul и @Mark подходы к непригодным для употребления предметам носят общий характер, но принимают O (N в квадрате), т. Е. Много.

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

import itertools

def allunique(L):
  # first try sets -- fastest, if all items are hashable
  try:
    return len(L) == len(set(L))
  except TypeError:
    pass
  # next, try sort -- second fastest, if items are comparable
  try:
    L1 = sorted(L)
  except TypeError:
    pass
  else:
    return all(len(list(g))==1 for k, g in itertools.groupby(L1))
  # fall back to the slowest but most general approach
  return all(v not in L[i+1:] for i, L in enumerate(L))

Это O (N), где это возможно (все элементы хешируемы), O (N log N) как наиболее частый запасной вариант (некоторые элементы не подлежат изменению, но все сопоставимы), O (N в квадрате), где это неизбежно (некоторые элементы не подлежат проверке, например, диктанты и некоторые несопоставимые, например, комплексные числа).

Вдохновение для этого кода происходит от старого рецепта великого Тима Питерса, который отличался тем, что фактически создавал список уникальных предметов (а также был так давно, что set не было рядом - он должен был использовать dict ...! -), но в основном столкнулись с идентичными проблемами.

Answer 3

Как насчет этого:

if len(x) != len(set(x)):
    raise Exception("throw to caller")

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

Answer 4

Надеемся, что все элементы в вашей последовательности неизменны - если нет, вы не сможете вызвать set в последовательности.

>>> set( ([1,2], [3,4]) )
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Если у вас есть изменяемые элементы, вы не можете их хешировать, и вам придется многократно проверять список:

def isUnique(lst):
    for i,v in enumerate(lst):
        if v in lst[i+1:]:
            return False
    return True

>>> isUnique( ([1,2], [3,4]) )
True
>>> isUnique( ([1,2], [3,4], [1,2]) )
False

Answer 5

При создании списка вы можете проверить, существует ли уже значение, например:

if x in y:
     raise Exception("Value %s already in y" % x)
else:
     y.append(x)

преимущество в том, что сообщается о конфликтующей переменной.

Answer 6

Я бы использовал это:

mylist = [1,2,3,4]
is_unique = all(mylist.count(x) == 1 for x in mylist)

Answer 7

Вы можете обработать список, чтобы создать уникальную копию:

def make_unique(seq): 
    t = type(seq) 
    seen = set()
    return t(c for c in seq if not (c in seen or seen.add(c)))

Или, если элементы seq не могут быть хешируемыми:

def unique1(seq):
    t = type(seq) 
    seen = [] 
    return t(c for c in seq if not (c in seen or seen.append(c)))

И это сохранит элементы в порядке (конечно, без дубликатов).