обработка индексов при вставке графа в python - PullRequest
Новая
       7

обработка индексов при вставке графа в python

0 голосов
/ 12 октября 2018

рассмотрим следующий список: 

["abc", "abx", "axx", "abx", "abc"]

теперь рассматриваем каждый элемент списка как вершину графа. Две вершины связаны, если два элемента отличаются только одним символом: 

abc > abx
abc > abx

и так далее. Итак, конечный результат будет: 

{"0":["1","3"],"1":["0","2","4"],"2":["1","3"],"3":["0","3","4"],"4":["1","3"]}

числа - это индексы. Я уже сделал функцию, чтобы проверить, должны ли быть соединены вершины
(этовозвращает логические значения), но основная проблема заключается в том, что в списке присутствует несколько элементов (в моем примере два abc и два abx). Проблема в том, что когда я хочу найти индекс иЭлемент наподобие «abc» .Python автоматически возвращает меньший индекс (то есть 0), но при сравнении «abx» с «abc» важны оба индекса (0 и 3). Это ужасно, так как есть C (5,2) =10 пар, которые нужно проверить.Я думаю, что каким-то образом я должен сказать Python проверить, есть ли более одного элемента, а также вспомнить, сколько раз он их использовал. Я действительно не знаю, как развить эту идею больше (также полезно ли это или нет)) и как выполнить это в коде.Спасибо за Ваше внимание.

1 Ответ

0 голосов
/ 12 октября 2018

Вы можете сделать следующее: 

from itertools import combinations as comb
from collections import defaultdict

# a,b are strings from the list, i,j are their respective indexes
edges = [(i,j) for (i,a),(j,b) in comb(enumerate(lst), 2) if len(set(a)-set(b))==1]
# [(0, 1), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)]

dd = defaultdict(list)
for i, j in edges:
    dd[i].append(j)
    dd[j].append(i)
# {0: [1, 3], 1: [0, 2, 4], 2: [1, 3], 3: [0, 2, 4], 4: [1, 3]}

Используется enumerate для получения индексов, itertools.combinations для получения всех возможных пар. Разница набора используется в условном понимании , чтобы отфильтровать все пары, отличающиеся ровно одной буквой, и collections.defaultdict для удобства построения окончательной структуры данных.от этих краев.

...