Есть ли функция, которая ищет последовательность элементов для подпоследовательности? Я ищу аналог StringPosition
для List
s. В моем текущем приложении я работаю с целыми списками, но меня бы интересовала общая функция FindSequence[list, pattern, n]
, которая найдет первые n
вхождения pattern
в List
.
Вот пример игрушки:
Сгенерируйте некоторые данные:
In[1]:= $HistoryLength = 0
Out[1]= 0
In[2]:= Timing[digits = First[RealDigits[\[Pi], 2, 10000000]];]
Out[2]= {26.5, Null}
Позвольте преобразовать его в строку, чтобы мы могли сравнить с StringPosition
. Это очень медленное голодание. (Память освобождается при завершении оценки.)
In[3]:= Timing[str = StringJoin[ToString /@ digits];]
Out[3]= {43.813, Null}
Я ищу эту подпоследовательность:
In[4]:= patt = {1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0,
1, 0, 1, 1};
In[5]:= strpatt = StringJoin[ToString /@ patt];
Поиск строки очень быстрый:
In[6]:= StringPosition[str, strpatt] // Timing
Out[6]= {1.047, {{5737922, 5737943}}}
Это простая реализация поиска численных массивов. Это медленнее, чем StringPosition
:
In[7]:= Timing[
corr = ListCorrelate[patt, digits];
Select[[email protected][corr, patt.patt],
digits[[# ;; # + Length[patt] - 1]] === patt &]
]
Out[7]= {2.234, {5737922}}
Резюме:
- Есть ли встроенный список, который ищет списки для подпоследовательностей?
- Если это не так, что такое быстрая и элегантная реализация для числовых списков (моя практическая проблема)?
- Как насчет общих списков, которые могут содержать что угодно? (Здесь есть две возможности: "статические" шаблоны, такие как
{1,0,1}
или общие, такие как{1,_,1}
, хотя эти последние могут вносить осложнения.)
Я ожидаю, что у этого будет много решений, некоторые быстрые, некоторые более элегантные, некоторые более общие: -)
Похожие вопросы:
- Быстрая реализация в Mathematica для Position2D (двумерный случай того же самого)
- Каков наилучший способ поиска периода (повторения) в Mathematica?
Интересное чтение:
EDIT:
Я только что нашел недокументированный LongestCommonSubsequencePositions
. LongestCommonSubsequencePositions[a, b]
найдет самую длинную общую подпоследовательность списков a
и b
и вернет позицию ее первого появления только в a
и b
. (Документированный LongestCommonSubsequence
, о котором я не знал, вернет только подпоследовательность, а не ее позицию.)
Он медленнее, чем альтернативы выше, но он работает с общими списками, которые могут содержать любое выражение.
In[57]:= LongestCommonSubsequencePositions[digits, patt] // Timing
Out[57]= {5.25, {{5737922, 5737943}, {1, 22}}}