Python: как найти «общие» части среди элементов списка?

Question

[Евгений Елизаров]

Всем привет. Требует помощь более умных товарищей. Есть задача - из списка составить список уникальных вхождений. Т.е. имеем список

list = [
u'DS4700_A2',
 u'DS4700_B2', 
u'FAS_8200_initiator1_0f', 
u'FAS_8200_initiator2_0f', 
u'FirstClass_8200_1_0e', 
u'FirstClass_8200_2_0e', 
u'HP3parInf_1', 
u'HP3parInf_2', 
u'HUS_CL7A', 
u'HUS_CL8A', 
u'HUS_new_CL7A', 
u'HUS_new_CL8A', 
u'NetApp_8200_1_0e', 
u'NetApp_8200_2_0e', 
u'StorwizeAdd_p1', 
u'StorwizeAdd_p2', 
u'Storwize_p1', 
u'Storwize_p2', 
u'fas2650_1', 
u'fas2650_2'
]

а на выходе хочется получить только уникальные общие вхождения

[
u'DS4700_',
u'FAS_8200_initiator, 
u'FirstClass_8200_', 
u'HP3parInf_', 
u'HUS_', 
u'HUS_new, 
u'NetApp_8200_, 
u'StorwizeAdd_p', 
u'Storwize_p', 
u'fas2650_', 
]

посмотрел в сторону difflib, но то ли лыжи не едут, то ли не там читал. помогите пожалуйста

Comments

[JaxxDexx]

Евгений Елизаров: Автор вы определитесь как вы определяете уникальные вхождения, а то так можно определить и "Storwize как уникальное вхождение для значений StorwizeAdd_p1, StorwizeAdd_p2 и Storwize_p1, Storwize_p2. Слишком неопределенное требование у вас

[Евгений Елизаров]

JaxxDexx: ну я же привёл пример

"Storwize" как уникальное вхождение для значений StorwizeAdd_p1, StorwizeAdd_p2 и Storwize_p1, Storwize_p2

вот так как раз не правильно. т.е. искать не наиболее короткое совпадение, а наиболее полное

[JaxxDexx]

Александр +: Извините, на вас подумал)))

[javedimka]

У тебя задача не из простых, ну в смысле не сама задача сложная, а просто потому что условия ты странно определил, например почему u'HUS_CL7A' и u'HUS_CL8A' обрезаются до HUS_, а u'StorwizeAdd_p1' и u'StorwizeAdd_p2' до StorwizeAdd_p? Какие критерии тут определяются? Если забить на это, то можно вообще по глупому сделать так:

import difflib


def find_common(seq):
    last = None
    new_seq = []
    for word in seq:
        if not last:
            last = word
            continue
        slices = difflib.SequenceMatcher(None, last, word).get_matching_blocks()
        new_seq.append(last[:slices[0].size])
        last = None
    return new_seq

>>> find_common(lst)
['DS4700_',
 'FAS_8200_initiator',
 'FirstClass_8200_',
 'HP3parInf_',
 'HUS_CL',
 'HUS_new_CL',
 'NetApp_8200_',
 'StorwizeAdd_p',
 'Storwize_p',
 'fas2650_']

[Евгений Елизаров]

javedimka: u'HUS_CL7A' и u'HUS_CL8A' - тут я просто ошибся, должно быть HUS_CL по аналогии с остальными конечно же. Да, сорри, сбил с толку.
Огромное спасибо за помощь, работает как надо!

[javedimka]

Евгений Елизаров: Замечу, что работать это будет до тех пор пока слова идут не в перемешку и до тех пор пока там всего два слова для сравнения.

[Евгений Елизаров]

Вот это конечно не очень хорошо, схема может и измениться.

[javedimka]

Евгений Елизаров: Тогда еще больше расстрою, работать функция сверху будет только если сравнение идет с начала слова =)

[Евгений Елизаров]

Значит будем искать и думать дальше

Answer 1

[JaxxDexx]

Вот вам ГОВНОКОДЕС, лень по уму делать, но и этот работает))

from collections import OrderedDict

src = [
	u'DS4700_A2',
	u'StorwizeAdd_p1',
	u'DS4700_B2',
	u'FAS_8200_initiator1_0f',
	u'FirstClass_8200_1_0e',
	u'FirstClass_8200_2_0e',
	u'HP3parInf_1',
	u'NetApp_8200_1_0e',
	u'HP3parInf_2',
	u'HUS_CL8A',
	u'HUS_new_CL7A',
	u'fas2650_2',
	u'HUS_new_CL8A',
	u'NetApp_8200_2_0e',
	u'StorwizeAdd_p2',
	u'Storwize_p1',
	u'Storwize_p2',
	u'FAS_8200_initiator2_0f',
	u'fas2650_1',
	u'HUS_CL7A',
	u'H'
]

src = list(set(src))
src.sort(key=lambda x: len(x), reverse=True)

src1 = {}
for i, s in enumerate(src):
	for j in range(0, len(s)):
		sn = s if not j else s[:-j]
		for s2 in src[i+1:]:
			for l in range(0, len(s)):
				sn1 = s2 if not l else s2[:-l]
				if sn == sn1:
					if sn not in src1:
						src1[sn] = set()
						src1[sn].add(s)
					src1[sn].add(s2)

src2 = OrderedDict(sorted(src1.items(), key=lambda t: len(t[0]), reverse=True))

src2_keys = list(src2.keys())
for i, k in enumerate(src2_keys):
	if k in src2.keys():
		if not len(src2[k]):
			src2.pop(k)
			continue

		if len(src2[k]) == 1:
			key = src2[k].pop()
			if k != key:
				src2[key] = key
				src2.pop(k)
			continue

		if i == len(src2_keys):
			break

		for value in src2[k]:
			is_break = False
			for j, k2 in enumerate(src2_keys[i+1:]):
				if value in src2[k2]:
					if len(src2[k]) == 1:
						src2.pop(k)
						is_break = True
						break
					else:
						src2[k2].remove(value)

			if is_break:
				break

print(src2.keys())

Comments

[Евгений Елизаров]

Так, вроде то что нужно, спасибо большое!

[JaxxDexx]

Косяки скорее всего все равно будут, т.к. налету писалось

[Евгений Елизаров]

JaxxDexx: Ну вот смотрю, пробую в различных вариантах, пока всё норм :)

[longclaps]

JaxxDexx:
Зашел посмотреть, отчего топикстартер затих, а тут опс!

src.sort(key=lambda x: len(x), reverse=True) # no
src.sort(key=len, reverse=True)              # yes

Но вообще молодцом. Я как-то так:

tree = {}
for w in src:
    while w:
        w = w[:-1]
        if w in tree:
            tree[w] += 1
            break
        else:
            tree[w] = 1
for w in sorted(tree.keys()):
    if w.endswith("_") and tree[w] > 1:
        print(w)

[JaxxDexx]

longclaps: За замечение по поводу key=len, спасибо :)

Answer 2

[Влад Григорьев]

Если не требуется порядка, то можно использовать множества.

b = {randint(1, 1000) for _ in range(100)}
b
{513, 17, 25, 26, 28, 46, 52, 54, 62, 63, 65, 581, 582, 72, 80, 82, 600, 601, 618, 625, 118, 639, 132, 649, 651, 142, 661, 662, 151, 168, 172, 685, 188, 701, 195, 708, 205, 211, 724, 214, 730, 741, 238, 760, 762, 255, 256, 767, 771, 779, 791, 792, 793, 280, 806, 295, 822, 311, 833, 835, 839, 331, 848, 343, 860, 349, 350, 367, 383, 897, 386, 900, 912, 914, 408, 419, 420, 935, 936, 425, 939, 430, 943, 432, 433, 435, 949, 956, 450, 452, 973, 976, 477, 478, 995, 486, 497, 501, 508}
a = {randint(1, 1000) for _ in range(100)}
a
{517, 7, 532, 534, 544, 35, 551, 49, 54, 571, 75, 78, 592, 601, 92, 114, 634, 123, 638, 128, 643, 653, 143, 149, 669, 162, 163, 168, 174, 176, 713, 207, 208, 209, 216, 730, 742, 235, 243, 758, 761, 773, 782, 784, 786, 281, 795, 798, 811, 308, 316, 320, 832, 322, 324, 842, 845, 359, 877, 367, 885, 379, 381, 902, 391, 906, 394, 910, 919, 924, 928, 930, 935, 936, 425, 941, 432, 952, 444, 447, 963, 458, 971, 466, 473, 986, 480, 996, 1000, 503, 504, 506}
a.intersection(b)
{935, 168, 936, 425, 367, 432, 54, 601, 730}

# Если требуется порядок
a = [randint(1, 1000) for _ in range(100)]
b = [randint(1, 1000) for _ in range(100)]
[v for v in a if v in b]
[9, 866, 611, 981, 775, 197, 813, 337, 78]

Answer 3

[aRegius]

Привет.
Пробуйте.

# my_list = your_list
>>> import itertools
>>> grouped_values = []
>>> my_values = []
>>> value = ''
>>> for _, group in itertools.groupby(my_list, len):
	        grouped_values.append(list(group))
	
>>> zipped_values = [list(zip(*i)) for i in grouped_values]
>>> for i in zipped_values:
	        for u in i:
		            if len(set(u)) == 1:
			                value += u[0]
		            else:
			                my_values.append(value)
			                value = ''
			                break
# for i in my_values: print(i)