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

Скажем, у меня есть массив/список вещей, которые я хочу сравнить. На языках, с которыми я знаком, я бы сделал что-то вроде

for (int i = 0, i < mylist.size(); i++)
    for (int j = i + 1, j < mylist.size(); j++)
        compare(mylist[i], mylist[j])

Это гарантирует, что мы сравниваем каждую пару раз. В каком-то контексте я выполняю обнаружение столкновений в связке объектов, содержащихся в списке. Для каждого обнаруженного столкновения в список добавляется небольшой объект "столкновения", описывающий столкновение, который затем выполняет другую процедуру, разрешая каждое столкновение (в зависимости от характера двух сталкивающихся объектов). Очевидно, я хочу только сообщать о каждом столкновении один раз.

Теперь, что такое питонический способ сделать это, поскольку Python предпочитает использовать итераторы, а не перебирать индексы?

У меня был следующий (багги) код:

for this in mylist:
    for that in mylist:
        compare(this, that)

Но это явно захватывает каждое столкновение дважды, что приводит к некоторому странному поведению при попытке их разрешить. Итак, каково здесь питоновское решение?

Ответ 1

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

Вы можете использовать магию itertools для создания всех возможных комбинаций:

import itertools
for a, b in itertools.combinations(mylist, 2):
    compare(a, b)

itertools.combinations будет связывать каждый элемент с другим элементом в итерабельном, но только один раз.

Вы все равно можете написать это, используя доступ к элементам на основе индекса, эквивалентный тому, к чему вы привыкли, используя вложенные циклы for:

for i in range(len(mylist)):
    for j in range(i + 1, len(mylist)):
        compare(mylist[i], mylist[j])

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

Ответ 2

Используйте itertools.combinations(mylist, 2)

mylist = range(5)
for x,y in itertools.combinations(mylist, 2):
    print x,y

0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

Ответ 3

Этот код будет считать частоту и удалять повторяющиеся элементы:

from collections import Counter

str1='the cat sat on the hat hat'

int_list=str1.split();

unique_list = []
for el in int_list:

    if el not in unique_list:
        unique_list.append(el)
    else:
        print "Element already in the list"

print unique_list

c=Counter(int_list)

c.values()

c.keys()

print c