Как удалить дубликаты в списке объектов без __hash__

У меня есть список пользовательских объектов, из которых я хочу удалить дубликаты. Обычно вы делаете это, определяя __eq__ и __hash__ для своих объектов, а затем берете set из списка объектов. Я определил __eq__, но не могу найти хороший способ реализации __hash__, чтобы он возвращал одно и то же значение для одинаковых объектов.

В частности, у меня есть класс, производный от класса Tree из набора инструментов ete3. Я определил два объекта равными, если их расстояние Робинсона-Фулдса равно нуль.

from ete3 import Tree

class MyTree(Tree):

    def __init__(self, *args, **kwargs):
        super(MyTree, self).__init__(*args, **kwargs)

    def __eq__(self, other):
        rf = self.robinson_foulds(other, unrooted_trees=True)
        return not bool(rf[0])

newicks = ['((D, C), (A, B),(E));',
           '((D, B), (A, C),(E));',
           '((D, A), (B, C),(E));',
           '((C, D), (A, B),(E));',
           '((C, B), (A, D),(E));',
           '((C, A), (B, D),(E));',
           '((B, D), (A, C),(E));',
           '((B, C), (A, D),(E));',
           '((B, A), (C, D),(E));',
           '((A, D), (B, C),(E));',
           '((A, C), (B, D),(E));',
           '((A, B), (C, D),(E));']

trees = [MyTree(newick) for newick in newicks]

print len(trees)       # 12
print len(set(trees))  # also 12, not what I want!

И print len(trees), и print len(set(trees)) возвращают 12, но это не то, что мне нужно, потому что несколько объектов равны друг другу:

from itertools import product
for t1, t2 in product(newicks, repeat=2):
    if t1 != t2:
        mt1 = MyTree(t1)
        mt2 = MyTree(t2)
        if mt1 == mt2:
            print t1, '==', t2

который возвращает:

((D, C), (A, B),(E)); == ((C, D), (A, B),(E));
((D, C), (A, B),(E)); == ((B, A), (C, D),(E));
((D, C), (A, B),(E)); == ((A, B), (C, D),(E));
((D, B), (A, C),(E)); == ((C, A), (B, D),(E));
((D, B), (A, C),(E)); == ((B, D), (A, C),(E));
((D, B), (A, C),(E)); == ((A, C), (B, D),(E));
((D, A), (B, C),(E)); == ((C, B), (A, D),(E));
((D, A), (B, C),(E)); == ((B, C), (A, D),(E));
((D, A), (B, C),(E)); == ((A, D), (B, C),(E));
((C, D), (A, B),(E)); == ((D, C), (A, B),(E));
((C, D), (A, B),(E)); == ((B, A), (C, D),(E));
((C, D), (A, B),(E)); == ((A, B), (C, D),(E));
((C, B), (A, D),(E)); == ((D, A), (B, C),(E));
((C, B), (A, D),(E)); == ((B, C), (A, D),(E));
((C, B), (A, D),(E)); == ((A, D), (B, C),(E));
((C, A), (B, D),(E)); == ((D, B), (A, C),(E));
((C, A), (B, D),(E)); == ((B, D), (A, C),(E));
((C, A), (B, D),(E)); == ((A, C), (B, D),(E));
((B, D), (A, C),(E)); == ((D, B), (A, C),(E));
((B, D), (A, C),(E)); == ((C, A), (B, D),(E));
((B, D), (A, C),(E)); == ((A, C), (B, D),(E));
((B, C), (A, D),(E)); == ((D, A), (B, C),(E));
((B, C), (A, D),(E)); == ((C, B), (A, D),(E));
((B, C), (A, D),(E)); == ((A, D), (B, C),(E));
((B, A), (C, D),(E)); == ((D, C), (A, B),(E));
((B, A), (C, D),(E)); == ((C, D), (A, B),(E));
((B, A), (C, D),(E)); == ((A, B), (C, D),(E));
((A, D), (B, C),(E)); == ((D, A), (B, C),(E));
((A, D), (B, C),(E)); == ((C, B), (A, D),(E));
((A, D), (B, C),(E)); == ((B, C), (A, D),(E));
((A, C), (B, D),(E)); == ((D, B), (A, C),(E));
((A, C), (B, D),(E)); == ((C, A), (B, D),(E));
((A, C), (B, D),(E)); == ((B, D), (A, C),(E));
((A, B), (C, D),(E)); == ((D, C), (A, B),(E));
((A, B), (C, D),(E)); == ((C, D), (A, B),(E));
((A, B), (C, D),(E)); == ((B, A), (C, D),(E));

Итак, мой вопрос:

  • Какой должна быть хорошая реализация __hash__ для моего случая, чтобы set(trees) работало?
  • Или как удалить объекты, которые равны из моего списка, не определяя __hash__?

person BioGeek    schedule 10.10.2017    source источник
comment
IMO, самый безопасный подход к решению этой и подобных проблем - определить каноническое представление для вашей структуры данных, а затем заставить проблемные операции использовать каноническое представление.   -  person Leon    schedule 10.10.2017
comment
Если вы можете гарантировать, что каждый экземпляр MyTree инициализируется строкой, почему бы не сохранить строку и не вернуть ее хэш в собственном методе __hash__().   -  person quamrana    schedule 10.10.2017
comment
@quamrana 2 MyTree объекты, инициализированные из разных строк (с разными хэш-значениями), могут сравниваться равными (как показано в примере)   -  person Leon    schedule 10.10.2017
comment
@quamrana, как я объяснил в своем вопросе, я знаю, что __hash__() используется в наборах в Python. Мой вопрос заключается именно в том, как реализовать допустимую функцию __hash__() для моего варианта использования ИЛИ как я могу обойти это.   -  person BioGeek    schedule 10.10.2017
comment
Вы пробовали просто перебирать и удалять дубликаты? Это не самый быстрый алгоритм, но в зависимости от того, сколько у вас деревьев, это может не иметь значения.   -  person Alex Hall    schedule 10.10.2017
comment
Хорошо, я вижу, что мое понимание требований к объектам, налагаемых sets, было неправильным. Из экспериментов кажется, что для деревьев нужно будет уметь преобразовывать данное дерево в стандартную форму и брать хэш стандартной формы. Но что это за форма, я пока не могу вам сказать. Хорошо, это то, что сказал @Leon. Можно ли отсортировать ветки?   -  person quamrana    schedule 10.10.2017
comment
@Leon, использующий каноническое представление, был хорошей идеей, но в конечном итоге зашел в тупик. Подробности см. в этом ответе.   -  person BioGeek    schedule 10.10.2017
comment
@AlexHall В итоге я воспользовался вашим предложением, подробности см. в этом ответе.   -  person BioGeek    schedule 10.10.2017
comment
Не уверен, что это возможный подход, но, возможно, представляя ваши деревья как рекурсивный замороженный набор замороженных наборов имен листьев. Я начал ответ на stackoverflow.com/q/46626414/1878788 на основе такого способа описания деревьев, но сделал не закончить (пока?).   -  person bli    schedule 11.10.2017
comment
Наконец, я сделал это (непосредственно с помощью замороженных наборов, поэтому не нужно определять собственный хэш): а>   -  person bli    schedule 12.10.2017