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

Question

Предположим, у меня есть один список, который содержит строки анаграммы.Например,

anList = ['aba','baa','aab','cat','tac','act','sos','oss']

И я хочу построить словарь, который содержит элемент этого списка в качестве ключа, и строки анаграммы этого элемента будут значениями этого ключа в виде списка. Также элементы, которые будут добавлены всписок не повторяется как еще один ключ этого словаря.Например, если в список добавлен «baa», список которого является значением ключа «aba», то «baa» не может быть добавлен в качестве ключа далее.Выходной словарь должен выглядеть следующим образом:

anDict = {'aba' : ['baa','aab'],'cat' : ['tac','act'],'sos' : ['oss']}

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

Как я могу это сделать

Answer 1

Вы можете сгруппировать ваши слова по количеству букв, используя объект Counter:

from collections import Counter
from itertools import groupby

sorted list = sorted(anList, key=Counter)
groups = [list(y) for x, y in groupby(sortedList, key=Counter)]
#[['aba', 'baa', 'aab'], ['cat', 'tac', 'act'], ['sos', 'oss']]

Теперь, преобразуйте список списков анаграмм в словарь:

{words[0]: words[1:] for words in groups}
#{'aba': ['baa', 'aab'], 'cat': ['tac', 'act'], 'sos': ['oss']}

Answer 2

Здесь объединяются оба порядка появления с возможностью их не сгруппированы вместе:

anagram_list = ['cat','aba','baa','aab','tac','sos','oss','act']

first_anagrams = {}
anagram_dict = {}

for word in anagram_list:
    sorted_word = ''.join(sorted(word))
    if sorted_word in first_anagrams:
        anagram_dict[first_anagrams[sorted_word]].append(word)
    else:
        first_anagrams[sorted_word] = word
        anagram_dict[word] = []

print(anagram_dict)

Выход

{'aba': ['baa', 'aab'], 'sos': ['oss'], 'cat': ['tac', 'act']}

где ключ всегда является первой анаграммой в порядке появления, и алгоритм строго O(n) для n слов пренебрежимо длинной длины.

---

Если вам нужны все анаграммы в списке, включая первую, это становится намного проще:

anagram_list = ['cat','aba','baa','aab','tac','sos','oss','act']

first_anagrams = {}
anagram_dict = defaultdict(list)

for word in anagram_list:
    anagram_dict[first_anagrams.setdefault(''.join(sorted(word)), word)].append(word)

Результат

defaultdict(<type 'list'>, 
    {'aba': ['aba', 'baa', 'aab'], 'sos': ['sos', 'oss'], 'cat': ['cat', 'tac', 'act']})

Answer 3

Вы можете использовать функцию groupby() в предварительно отсортированном списке.Функция sorted (или Counter) может использоваться в качестве ключа для сортировки и группировки:

from itertools import groupby

anList = ['aba', 'baa', 'aab', 'cat', 'tac', 'act', 'sos', 'oss']

{k: v for _, (k, *v) in groupby(sorted(anList, key=sorted), key=sorted)}
# {'aba': ['baa', 'aab'], 'cat': ['tac', 'act'], 'sos': ['oss']}

Answer 4

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

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

from collections import defaultdict

anagrams = ['aba','baa','aab','cat','tac','act','sos','oss']

d = defaultdict(list)
for a in anagrams:
    key = ''.join(sorted(a))
    if key != a:
        d[key].append(a)

print(d)
# {'aab': ['aba', 'baa'], 'act': ['cat', 'tac'], 'oss': ['sos']}

Предостережения:

• всегда использует восходящую отсортированную версиюанаграммы в качестве ключа dict, который не является точным соответствием для выходных данных примера в вопросе
• , если отсортированной по возрастанию версии анаграммы нет в списке, этот подход добавит ранее несуществующуюанаграмма как ключ к диктовке

Answer 5

anList = ['aba', 'baa', 'aab', 'cat', 'tac', 'act', 'sos', 'oss']

anDict = {}
for word in anList:
    sorted_word = ''.join(sorted(word))
    found_key = [key  for key in anDict.keys() if sorted_word  == ''.join(sorted(key))]
    if found_key:
        anDict[found_key[0]].append(word)
    else:
        anDict[word]=[]


>>> anDict
{'aba': ['baa', 'aab'], 'cat': ['tac', 'act'], 'sos': ['oss']}

Answer 6

Простая версия без itertools.

Создание мультикарты sorted string -> [anagram string]:

>>> L = ['aba', 'baa', 'aab', 'cat', 'tac', 'act', 'sos', 'oss']
>>> d = {}
>>> for v in L:
...     d.setdefault("".join(sorted(v)), []).append(v)
...
>>> d
{'aab': ['aba', 'baa', 'aab'], 'act': ['cat', 'tac', 'act'], 'oss': ['sos', 'oss']}

Теперь, когда вы сгруппировали анаграммы, используйте первые значения в качестве ключа возвращаемого слова:

>>> {v[0]:v[1:] for v in d.values()}
{'aba': ['baa', 'aab'], 'cat': ['tac', 'act'], 'sos': ['oss']}

Answer 7

Вы можете использовать else с циклом for для достижения этого:

anList = ['aba','baa','aab','cat','tac','act','sos','oss']
anDict = dict()

for k in anList:
        for ok in anDict:
            if (ok == k): break
            if (sorted(ok) == sorted(k)):
                anDict[ok].append(k)
                break
        else:
            anDict[k] = []

print(anDict)
# {'aba': ['baa', 'aab'], 'cat': ['tac', 'act'], 'sos': ['oss']}

Answer 8

Вот медленный, но рабочий код:

anList = ['aba', 'baa', 'aab', 'cat', 'tac', 'act', 'sos', 'oss']
anDict = {}
for i in anList:
    in_dict = False
    for j in anDict.keys():
        if sorted(i) == sorted(j):
            in_dict = True
            anDict[j].append(i)
            break
    if not in_dict:
        anDict[i] = []