Подсчет строк в списках, а затем фильтрация и сопоставление в Python

Question

У меня есть список слов, и с помощью python3 я подсчитываю разницу в буквах между каждой комбинацией слов (используя умный алгоритм diff_summing с этого сайта ):

import itertools

def diff_letters(a,b):
    return sum ( a[i] != b[i] for i in range(len(a)) )

w = ['AAHS','AALS','DAHS','XYZA']

for x,y in itertools.combinations(w,2):
    if diff_letters(x,y) == 1:
        print(x,y)

Это печатает:

AAHS AALS
AAHS DAHS

Мой вопрос: Как мне подсчитать и запись о том, что строки «DAHS» и «AALS» имеют ровно одного партнера, и «AAHS»имеет двух партнеров? Я буду фильтровать для направленных комбинаций, где у каждого target_string есть ровно один near_matching_word, поэтому мои окончательные данные (в виде JSON) будут выглядеть так:

[
 {
   "target_word": "DAHS",
   "near_matching_word": "AAHS"
 },
 {
   "target_word": "AALS",
   "near_matching_word": "AAHS"
 }
]

(заметив, что AAHS не отображается как target_word)

У меня есть одна версия, использующая functools.reduce

import itertools
import functools
import operator

def diff_letters(a,b):
    return sum ( a[i] != b[i] for i in range(len(a)) )

w = ['AAHS','AALS','DAHS','XYZA']

pairs = []
for x,y in itertools.combinations(w,2):
    if diff_letters(x,y) == 1:
        #print(x,y)
        pairs.append((x,y))

full_list = functools.reduce(operator.add, pairs)
for x in full_list:
    if full_list.count(x) == 1:
        print (x)

, которая печатает

AALS
DAHS

но тогда мне придется вернуться к моему большому списку pairs, чтобы найти near_matching_word. Конечно, в моей окончательной версии список pairs будет намного больше, и target_word может быть первым или вторым элементом в кортеже (x, y).

Answer 1

Остальные ответы сохраняют все пары, даже если найдено более одного. Так как они не нужны, это, кажется, тратит память. Этот ответ содержит не более одной пары для каждой строки.

import collections
import itertools

def diff_letters(a,b):
    return sum ( a[i] != b[i] for i in range(len(a)) )

w = ['AAHS','AALS','DAHS','XYZA']

# Marker for pairs that have not been found yet.
NOT_FOUND = object()

# Collection of found pairs x => y. Each item is in one of three states:
# - y is NOT_FOUND if x has not been seen yet
# - y is a string if it is the only accepted pair for x
# - y is None if there is more than one accepted pair for x
pairs = collections.defaultdict(lambda: NOT_FOUND)

for x,y in itertools.combinations(w,2):
    if diff_letters(x,y) == 1:
        if pairs[x] is NOT_FOUND:
            pairs[x] = y
        else:
            pairs[x] = None
        if pairs[y] is NOT_FOUND:
            pairs[y] = x
        else:
            pairs[y] = None

# Remove None's and change into normal dict.
pairs = {x: y for x, y in pairs.items() if y}

for x, y in pairs.items():
    print("Target = {}, Only near matching word = {}".format(x, y))

Вывод:

Target = AALS, Only near matching word = AAHS
Target = DAHS, Only near matching word = AAHS

Answer 2

import itertools
import functools
import operator


def diff_letters(a, b):
    return sum(a[i] != b[i] for i in range(len(a)))


w = ['AAHS', 'AALS', 'DAHS', 'XYZA']

pairs = []
for x, y in itertools.combinations(w, 2):
    if diff_letters(x, y) == 1:
        pairs.append((x, y))

full_list = functools.reduce(operator.add, pairs)

result = []

for x in set(full_list):
    if full_list.count(x) == 1:
        pair = next((i for i in pairs if x in i))
        match = [i for i in pair if i != x][0]
        result.append({
            "target_word": x,
            "near_matching_word": match
        })

print(result)

Выходы:

[{'target_word': 'DAHS', 'near_matching_word': 'AAHS'}, {'target_word': 'AALS', 'near_matching_word': 'AAHS'}]

Answer 3

Вы можете использовать словарь вместо списка пар:

pairs = {}
for x, y in itertools.combinations(w, 2):
    if diff_letters(x, y) == 1:
        pairs.setdefault(x, []).append(y)
        pairs.setdefault(y, []).append(x)

result = [{ "target_word": key, "near_matching_word": head, } for key, (head, *tail) in pairs.items() if not tail]

print(result)

Выход

[{'target_word': 'AALS', 'near_matching_word': 'AAHS'}, {'target_word': 'DAHS', 'near_matching_word': 'AAHS'}]

В словаре pairs ключи являютсяtarget_words и значения near_matching_words. Затем используйте понимание списка, чтобы отфильтровать те, которые имеют более 1 near_matching_word.