список строк - удалить общие черты общих строк

Question

Я изо всех сил пытаюсь решить эту проблему (и как придумать имя для этого вопроса в stackoverflow).

Мне нужно как-то удалить общности строк, сохраняя остаток.

Учитывая список таких как:

l = ('first', 
    'first.second', 
    'first.second.third', 
    'a.b.c', 
    'x.y.z', 
    'x.y') 

Я надеюсь иметь выход список как:

('first', 
'second', 
'third', 
'a.b.c', 
'x.y', 
'z') 

, как вы можете видеть, когда first.second вычитает first и остается second. first.second вычитается из first.second.third, мы получаем third. a.b.c не имеет ничего, чтобы вычесть из себя, поэтому он остается. x.y вычитается из x.y.z и z остается.

Я думаю, что, возможно, sort(key=len) будет частью решения, а также какой-то рекурсии, чтобы в итоге получить остаток строки. Я надеюсь на чистый способ удалить общие черты каждой строки в списке.

Answer 1

Я думал об этой интересной проблемы еще немного и придумал решение.

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

• фактического типа данных дерева (которое, как я сначала решил, но он был гораздо более многословны)
• рекурсия
• имитация рекурсии с использованием стеков (что я и закончил в конечном итоге).

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

li = ['First', 
     'FirstSecond', 
     'FirstSecondFirst', 
     'FirstSecondFirstly', 
     'FirstSecondThird', 
     'FirstFoo', 
     'FirstBarracudaSphyraena', 
     'xyz', 
     'xy', 
     '12345', 
     '123', 
     '1', 
     'FireTruckGarage', 
     'FireTruck', 
     'Fire'] 

Хитрость заключается в заметив, что каждый раз, когда есть потенциал удлинение префикса, мы должны сохранить предыдущий префикс в стеке префикса (здесь prefixes), который содержит все префиксы, которые до сих пор не исчерпаны. После того, как мы сделали некоторые из «более глубоких» слов - в смысле того, чтобы быть узлами глубже по дереву, нам может потребоваться отступить и снова использовать старый префикс для более короткого слова.

После того, как встречается слово, которое не префикс текущего префикса, мы должны выставить стек префиксов, пока мы не достигнем того, что делает префикс слова и продолжить оттуда.

def ambiguate(words): 
    output = {} 
    prefixes = [''] 
    prefix = prefixes[0] 

    for item in sorted(set(words)): 
     backtracked = False 

     while not item.startswith(prefix): 
      prefix = prefixes.pop() 
      backtracked = True 

     # If we have backtracked, we put back the current prefix onto the 
     # prefix stack since we may have to use it later on. 
     if backtracked: 
      prefixes.append(prefix) 

     # Construct new output and a new prefix and append it to the 
     # prefix stack 
     output[item] = item.replace(prefix, '', 1) 
     prefix = item 
     prefixes.append(prefix) 

    return output 

Продолжительность:

print(ambiguate(li)) 

Урожайность:

{'1': '1',          
'123': '23',          
'12345': '45',         
'Fire': 'Fire',         
'FireTruck': 'Truck',       
'FireTruckGarage': 'Garage',      
'First': 'First',        
'FirstBarracudaSphyraena': 'BarracudaSphyraena', 
'FirstFoo': 'Foo',        
'FirstSecond': 'FirstSecond',     
'FirstSecondFirst': 'First',      
'FirstSecondFirstly': 'ly',      
'FirstSecondFourth': 'Fourth',     
'FirstSecondThird': 'FirstSecondThird',   
'a': 'a',          
'abc': 'bc',          
'xy': 'xy',          
'xyz': 'z'} 

Answer 2

Я считаю, что вам нужно скорее определить свою проблему, прежде чем писать решение. Вот что я делаю из вашего тестового примера:

1. «Участники» разделены по периодам: тот же «член» не может отображаться в двух элементах кортежа.
2. Каждый член должен появляться только один раз.

Проблема заключается в том, что приоритет неоднозначен. Например, в следующей последовательности:

lst = ('a.b.c', 
     'a.b.d') 

Где находятся «а» и «b»? В вашем тестовом примере подразумевается, что общий член должен перейти на тот, у которого есть наименее общие члены (так что «z» не остается с «x.y.z»), но есть много крайних случаев, которые необходимо учитывать. Вам нужно будет указать свои требования в более точном формате.

Принятие гораздо более простое правило, что «член» должен оставаться в первую очередь, что кажется, следующая функция делает трюк:

def remove_common(lst): 
    seen = set() 
    res = [] 
    for i in lst: 
     members = i.split('.') 
     res.append('.'.join(w for w in members if w not in seen)) 
     seen |= set(members) 
    return tuple(res) 

Это дает результат очень близкий к вашему:

>>> remove_common(l) 
('first', 'second', 'third', 'a.b.c', 'x.y.z', '') 

Answer 3

Если выходной порядок не важен, это решение даст вам ожидаемые значения.

Это реализация почти такая же, как ответ на @ brianpck. Но я использовал сортировку для решения проблемы "x.y.z". И некоторые дополнительные объяснения.

l = ('first', 
    'first.second', 
    'first.second.third', 
    'a.b.c', 
    'x.y.z', 
    'x.y') 

def clarify(lst): 

    # Sort the list to deal with the order problem. 
    # for ex. "x.y.z" deletes "x.y" if not sorted 
    lst = sorted(lst) 

    # Words encountered. 
    words = set() 

    new_list = [] 

    for elem in lst: 

     # Divide elements using dots. 
     divided = elem.split(".") 

     # New element to be added to the result. 
     new_elem = [] 

     # For each word in a divided element. 
     for word in divided: 
      # If a word in the element is not encountered before. 
      # Add it to new element 
      # Add it to words 
      if word not in words: 
       new_elem.append(word) 
       words.add(word) 
     # Join new element 
     new_list.append(".".join(new_elem)) 

    return new_list 

print clarify(l) 

# Gives ['a.b.c', 'first', 'second', 'third', 'x.y', 'z'] 
# You can make this a tuple in the solution as in the input if you want. 

Answer 4

Я думаю, что, может быть, я тоже пытался слишком поучиться со списком и пониманием диктата.

Я считаю, что я был в состоянии решить эту проблему следующим:

1. сортировать в переплете список
2. использовать переменную для «предыдущего элемента списка»
3. цикла, и выход на текущий элемент замены предыдущего элемента (если он найден)

Вот что я до сих пор:

li = [ 
    'first', 
    'first.second', 
    'first.second.third', 
    'a', 
    'a.b', 
    'a.b.c', 
    'x.y.z', 
    'x.y'] 

li.sort() 

prev_l = '' 
output = {} 
for l in li: 
    if l.find(prev_l) ==0: 
     output[l] = l.replace(prev_l,'') 
    else: 
     output[l] = l 
    prev_l = l 

выход:

{ 
'a'     : 'a', 
'a.b'    : '.b', 
'a.b.c'    : '.c', 
'first'    : 'first', 
'first.second'  : '.second', 
'first.second.third' : '.third', 
'x.y'    : 'x.y', 
'x.y.z'    : '.z'}