В настоящее время я ищу способ поиска шаблонов в списке целых чисел, но метод, который я собираюсь использовать, применим к строкам и другим спискам с разными элементами, конечно. Теперь позвольте мне объяснить, что я ищу.
Я хочу найти самый длинный повторяющийся шаблон в списке целых чисел. Например,
[1, 2, 3, 4, 1, 2, 3]
# This list would give 1, 2, 3
Перекрывающиеся шаблоны должны быть отброшены. (Не определенно)
[1, 1, 1, 1, 1]
# Should give 1, 1 Not 1, 1, 1, 1
Вот что мне не помогло.
Поиск шаблонов в списке (Не понял логику первого ответа, очень мало объяснений. И второй ответ решает проблему только в том случае, если шаблон известен до решение.)
Поиск целочисленного шаблона из списка (Шаблон задан и требуется количество вхождений. Отличается от моего вопроса.)
Самая длинная общая проблема подпоследовательности (Большинство людей занимались этой проблемой, однако она не близка мне. Мне нужны последовательные элементы при поиске Однако в этом отдельные элементы также учитываются как подпоследовательности.)
Вот что я пробовал.
def pattern(seq):
n = len(seq)
c = defaultdict(int) # Counts of each subsequence
for i in xrange(n):
for j in xrange(i + 1, min(n, n / 2 + i)):
# Used n / 2 because I figured if a pattern is being searched
# It cant be longer that the half of the list.
c[tuple(seq[i:j])] += 1
return c
Как вы видите, он находит все подсписки и проверяет повторы. Я нашел этот подход немного наивным (и неэффективным), и мне нужен лучший способ. Пожалуйста, помогите мне. Спасибо заранее.
Примечание1: Список предопределен, но из-за отказа моих алгоритмов я могу только проверить некоторые части списка перед замораживанием компьютера. Таким образом, шаблон, который я пытаюсь найти, может быть намного длиннее половины списка поиска. Он может даже быть длиннее самого списка поиска, потому что я ищу только часть исходного списка. Если вы представляете лучший метод, чем Я использую, я могу искать большую часть исходного списка, поэтому у меня будет больше шансов найти шаблон. (Если он есть.)
Примечание2: Вот часть списка, если вы хотите протестировать его самостоятельно. Кажется, что есть шаблон, но я не могу быть уверен, прежде чем тестировать его с помощью надежного кода. Пример списка
Примечание3: Я рассматриваю это как серьезную проблему интеллектуального анализа данных. И попробуем узнать, если вы сделаете длинное объяснение. Это похоже на гораздо более важную проблему, чем LCS, однако LCS гораздо более популярен: D Этот метод, который я пытаюсь найти, похож на методы, которые ученые используют для поиска ДНК-образцов.
