Как сделать уникальный список вложенных словарей в Python

Question

У меня есть следующий список вложенных словарей:

[{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-545', 
       'name': 'Users', 
       'type': 'group'}}, 
{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-545', 
       'name': 'Users', 
       'type': 'group'}}, 
{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-544', 
       'name': 'Administrators', 
       'type': 'group'}}] 

Я хочу, чтобы сделать его уникальным и пробовал разные предложения, но безуспешно. Может ли кто-нибудь помочь сделать его уникальным в python 2.6? В приведенных выше данных нет ключевого/уникального поля. Я ожидаю, что следующий результат (один член списка удаляется как полный дубликат):

[{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-545', 
       'name': 'Users', 
       'type': 'group'}}, 
{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-544', 
       'name': 'Administrators', 
       'type': 'group'}}] 

Answer 1

Вы должны были бы отслеживать, если вы уже видели словарь уже. К сожалению, словари не хешируются и не отслеживают порядок, поэтому вам нужно конвертировать словари в нечто, что is hashable. frozenset() из пар ключ-значение (как кортежей) будет делать, но тогда вам нужно расплющить рекурсивно:

def set_from_dict(d): 
    return frozenset(
     (k, set_from_dict(v) if isinstance(v, dict) else v) 
     for k, v in d.iteritems()) 

Эти frozenset() объекты представляют словарные значения достаточно для отслеживания уникальных предметов:

seen = set() 
result = [] 
for d in inputlist: 
    representation = set_from_dict(d) 
    if representation in seen: 
     continue 
    result.append(d) 
    seen.add(representation) 

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

Приведенный выше подход использует O (N) время, один шаг для каждого словаря ввода, поскольку тестирование против множества принимает только O (1) постоянное время.

Демо:

>>> inputlist = [{'permission': 'full', 
... 'permission_type': 'allow', 
... 'trustee': {'id': 'SID:S-1-5-32-545', 
...    'name': 'Users', 
...    'type': 'group'}}, 
... {'permission': 'full', 
... 'permission_type': 'allow', 
... 'trustee': {'id': 'SID:S-1-5-32-545', 
...    'name': 'Users', 
...    'type': 'group'}}, 
... {'permission': 'full', 
... 'permission_type': 'allow', 
... 'trustee': {'id': 'SID:S-1-5-32-544', 
...    'name': 'Administrators', 
...    'type': 'group'}}] 
>>> def set_from_dict(d): 
...  return frozenset(
...   (k, set_from_dict(v) if isinstance(v, dict) else v) 
...   for k, v in d.iteritems()) 
... 
>>> seen = set() 
>>> result = [] 
>>> for d in inputlist: 
...  representation = set_from_dict(d) 
...  if representation in seen: 
...   continue 
...  result.append(d) 
...  seen.add(representation) 
... 
>>> from pprint import pprint 
>>> pprint(result) 
[{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-545', 'name': 'Users', 'type': 'group'}}, 
{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-544', 
       'name': 'Administrators', 
       'type': 'group'}}] 

Answer 2

Ваши пункты dict так что вы не сможете использовать set напрямую (проверьте frozenset или this question/answer).
Но вы все еще можете сравнить элементы:

>>> l[0]==l[1] 
True 
>>> l[0]==l[2] 
False 

Так просто добавить свои элементы в новый список, если он еще не присутствует:

>>> l2=[] 
>>> for i in l: 
... if i not in l2: 
...  l2.append(i) 
... 
>>> pprint(l2) 
[{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-545', 'name': 'Users', 'type': 'group'}}, 
{'permission': 'full', 
    'permission_type': 'allow', 
    'trustee': {'id': 'SID:S-1-5-32-544', 
       'name': 'Administrators', 
       'type': 'group'}}]