Удалить элемент из списка на основе следующего элемента в том же списке

Ответ 1

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

Ошибка возникла из-за того, что вы изменяли один и тот же список при проверке индекса с помощью range().

Таким образом, увеличивая переменную i вы удаляете элемент из списка, который в какой-то момент неизбежно вызывает index error.

Таким образом, вот рабочая версия вашего исходного кода с некоторыми изменениями,

pattern = ["ABCDE","ABCDEFG","ABCDEFGH","ABCDEFGHIJKLMNO","CEST","DBTSFDE","DBTSFDEO","EOEUDNBNUW","EAEUDNBNUW","FG","FGH"]
output_pattern = []


for i in range(0, (len(pattern)-1)):
    if not pattern[i] in pattern[i+1]:
        output_pattern.append(pattern[i]) 

# Adding the last item
output_pattern.append(pattern[-1])   
print (output_pattern)

>>>> ['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']    

Обратите внимание, что этот код будет работать, если ваш список был ранее отсортирован, как вы упомянули в разделе комментариев.

Что делает этот код?

В основном, он использует ту же логику вашего первоначального ответа, где он итерации в списке, и проверьте, содержит ли следующий элемент текущий элемент. Но, используя другой список и итерацию до последнего элемента, устранить проблему с индексом. Но теперь возникает вопрос,

Что мне делать с последним элементом?

Поскольку список отсортирован, вы можете считать последний элемент уникальным. Вот почему я использую

output_pattern.append(pattern[-1])

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

Важная заметка

Этот ответ был написан в ответ на первоначальный вопрос OP, где он хотел сохранить более длительное совпадение, и я цитирую, основываясь на следующем элементе в том же списке. Как указано в @Chris_Rands, если ваши проблемы связаны с биологической задачей и необходимо найти какое-либо перекрытие, это решение не подходит для ваших нужд.

Пример, когда этот код не смог бы распознать потенциальное перекрытие,

pattern = ["ACD", "AD", "BACD"]

где он выдаст тот же результат без удаления возможного перекрытия "ACD". Теперь, как пояснение, это будет означать гораздо более сложный алгоритм, и я изначально думал, что это выходит за рамки требований к вопросу. Если когда-либо это ваш случай, я могу быть совершенно неправым здесь, но я действительно считаю, что реализация C++ представляется более уместной. взгляните на алгоритм CD-Hit, предложенный @Chris_Rands в разделе комментариев.

Ответ 2

Вы можете использовать groupby() и max() чтобы помочь здесь:

from itertools import groupby

with open('toy.txt') as f_input:
    for key, group in groupby(f_input, lambda x: x[:2]):
        print(max(group, key=lambda x: len(x)).strip())

Это отобразится:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EOEUDNBNUW
EAEUDNBNUW
FGH

groupby() работает, возвращая список совпадающих элементов на основе функции, в этом случае последовательные строки с теми же первыми двумя символами. Затем функция max() берет этот список и возвращает элемент списка с самой длинной длиной.

Ответ 3

# assuming list is sorted:
pattern = ["ABCDE",
"ABCDEFG",
"ABCDEFGH",
"ABCDEFGHIJKLMNO",
"CEST",
"DBTSFDE",
"DBTSFDEO",
"EOEUDNBNUW",
"EAEUDNBNUW",
"FG",
"FGH"]

pattern = list(reversed(pattern))

def iterate_patterns():
    while pattern:
        i = pattern.pop()
        throw_it_away = False
        for p in pattern:
            if p.startswith(i):
                throw_it_away = True
                break
        if throw_it_away == False:
            yield i

print(list(iterate_patterns()))

Выход:

['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']

Ответ 4

with open('demo.txt') as f:
    lines = f.readlines()

l_lines = len(lines)

n_lst = []

for i, line in enumerate(lines):
    line = line.strip()
    if i == l_lines - 1:
        if lines[-2] not in line:
            n_lst.append(line)
        break
    if line not in lines[i + 1]:
        n_lst.append(line)

print(n_lst)

Выход

['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']

Ответ 5

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

class Tree:
  def __init__(self, val=None):
    self.left, self.value, self.right = None, val, None
  def insert_val(self, _val):
    if self.value is None or _val.startswith(self.value):
       self.value = _val
    else:
       if _val < self.value:
          getattr(self.left, 'insert_val', lambda x:setattr(self, 'left', Tree(x)))(_val)
       else:
          getattr(self.right, 'insert_val', lambda x:setattr(self, 'right', Tree(x)))(_val)
  def flatten(self):
     return [*getattr(self.left, 'flatten', lambda :[])(), self.value, *getattr(self.right, 'flatten', lambda :[])()]

t = Tree()
for i in open('filename.txt'):
  t.insert_val(i.strip('\n'))
print(t.flatten())

Выход:

['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EAEUDNBNUW', 'EOEUDNBNUW', 'FGH']

Ответ 6

Это позволит вам, где вы хотите быть:

with open('toy.txt' ,'r') as f:
    lines = f.readlines()
    data = set(lines)
    print(sorted([i for i in lines if len([j for j in data if j.startswith(i)])==1]))

#['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EAEUDNBNUW', 'EOEUDNBNUW', 'FGH']

Я добавил set только в случае нескольких вхождений одного и того же текста.

Ответ 7

Простым способом является обработка входного файла по одной строке за раз, сравните каждую строку с предыдущей и сохраните предыдущую, если она не содержится в текущей.

Код может быть простым:

with open('toy.txt' ,'r') as f:
    old = next(f).strip()               # keep first line after stripping EOL 

    for pattern in f:
        pattern = pattern.strip()       # strip end of line...
        if old not in pattern:
            print old                   # keep old if it is not contained in current line
        old = pattern                   # and store current line for next iteration
    print old                           # do not forget last line

Ответ 8

Не точное соответствие вашим ожиданиям, но, учитывая, что вы заявляете, что он отсортирован (и это не так, около EOEUDNBNUWD EAEUDNBNUW) и что я не знаю, почему вам не хватает EOEUDNBNUWD Я не уверен, правильно ли указаны ваши ожидания или если Я неправильно понял ваш вопрос.

(ах, да, я вижу, что понятие перекрытия бросает ключ в sort и startswith).

Может быть приятно, чтобы OP повторил этот конкретный аспект, я прочитал комментарий @DSM, не понимая его проблемы. Теперь я это делаю.

li = sorted([i.strip() for i in """
ABCDE
ABCDEFG
ABCDEFGH
ABCDEFGHIJKLMNO
CEST
DBTSFDE
DBTSFDEO
EOEUDNBNUW
EOEUDNBNUWD
EAEUDNBNUW
FEOEUDNBNUW
FG
FGH""".splitlines() if i.strip()])

def get_iter(li):
    prev = ""
    for i in li:
        if not i.startswith(prev):
            yield(prev)
        prev = i
    yield prev

for v in get_iter(li):
    print(v)

выход:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
EOEUDNBNUWD
FEOEUDNBNUW
FGH

Ответ 9

Код

import collections as ct


def read_file(filepath):
    """Yield a generator of lines from a file."""
    with open(filepath, "r") as f:
        for line in f:
            yield line.strip()


def find_longest_sequences(seqs):
    """Return a dict of the long common sequences."""
    seqs = tuple(seqs) 
    dd = ct.defaultdict(list)
    [dd[k].append(seq) for seq in seqs for k in seqs if k in seq]
    return {max(v, key=len) for v in dd.values()}


data = read_file("test.txt")
find_longest_sequences(data)

Выход

{'ABCDEFGHIJKLMNO',
 'CEST',
 'DBTSFDEO',
 'EAEUDNBNUW',
 'EOEUDNBNUWD',
 'FEOEUDNBNUW'}

подробности

Мы используем read_file для каждой строки файла.

find_longest_sequences строит defaultdict, который группирует аналогичные последовательности вместе. Он выполняет итерацию данных с помощью двух циклов:

1. В первом цикле строит список пустых списков с уникальными последовательностями в виде ключей.
2. Второй цикл добавляет в качестве значений любые строки, похожие на ключ.

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

Обратите внимание на некоторые несоответствия с ожидаемым результатом:

1. FGH перекрывается с ABCDEFGHIJKLMNO и, следовательно, не является допустимым выходом.
2. FEOEUDNBNUWD не является исходной последовательностью. Пост-обработка необходима для перекрывающихся последовательностей.

Ответ 10

Кенни, ты почти понял это, но есть две проблемы, которые @scharette указал:

1. for цикла и удаления элемента списка не должны идти вместе. Исправление использовать while цикл и явно увеличить индекс. В while петля является менее эффективной, так как он вызывает len() несколько раз, а не один раз, но то, что нужно, чтобы получить правильный результат.
2. IndexError. Это происходит только в последней строке. Мой способ справиться с этой проблемой - игнорировать ошибку.

При этом я изменил ваш код на:

with open('toy.txt' ,'r') as f:
    pattern = f.read().splitlines()
    print pattern

    try:
        i = 0
        while i < len(pattern):
            if pattern[i] in pattern[i+1]:
                pattern.remove(pattern[i])
            print pattern
            i += 1
    except IndexError:
        pass

Ответ 11

Как указано в других ответах, ваша ошибка возникает из расчета длины вашего ввода в начале и затем не обновляя его при сокращении списка.

Вот еще один пример:

with open('toy.txt', 'r') as infile:
    input_lines = reversed(map(lambda s: s.strip(), infile.readlines()))

output = []
for pattern in input_lines:
    if len(output) == 0 or not output[-1].startswith(pattern):        
        output.append(pattern)

print('\n'.join(reversed(output)))