在列表中查找相同或相似的序列

如果列表中有兩個非重疊的序列並且具有某個屬性，那麼我需要將列表轉換爲空列表。例如。在這種情況下，等於和長度> = 2）在列表中查找相同或相似的序列

mm[{___, b1__, ___, b1__, ___}] := {} /; Length[{b1}] >= 2

，或者例如2子列表，具有相似功能等於0和 Legth = 4

mm[{___, b1__, ___, b2__, ___}] := {} /; 
NeedlemanWunschSimilarity[{b1}, {b2}] == 0 && Length[{b1}] == 4 && 
Length[{b2}] == 4

等等... ..

對於mathematica，誰知道內部算法的大師，有沒有更快的的方式，也許使用PatternTest（？）？

來源

2011-11-24 user1063646

列表中的元素是什麼？你能提供樣品清單嗎？您需要使用的最大序列長度是多少？ – Szabolcs

我總是測試一個二進制列表，例如{0,1,0,1，.......，0}，並且如果2個非重疊部分（不總是具有相同的長度），我需要測試False或True ）是另一個的簡單轉換。我的意思是「轉換」，如平等（無轉換），旋轉，倒置等等，或者有更快的方法來做到這一點？ – user1063646

爲了真正得到一個有效的解決方案，您需要提供一個函數，將您的序列帶入一些規範形式，對於您感興趣的每個轉換。否則，任何解決方案都必須執行配對比較，這意味着它將是'O （n^2）'如果'n'是列表的長度。人們可以使用一些技巧來優化n^2前面的常數因子（在某些情況下可能非常重要），但是對於真正大的列表來說，這無關緊要。 –

我在等待着你在做什麼更詳細的描述，但在平均時間：

mm2[{___, b1 : Repeated[_, {4}], ___, b2 : Repeated[_, {4}], ___}] := {} /; 
    NeedlemanWunschSimilarity[{b1}, {b2}] == 0

這使用Repeated測試正確長度的唯一序列。

您可以用Repeated[_, {min, max}]指定最小和最大序列長度。

來源

2011-11-24 10:39:28

我的任務是標記一個列表，當兩個不重疊的子序列是一個時，另一個的變換即基本相等，一個是另一個的旋轉，另一個是另一個的反轉，依此類推。在我看來，___表示法非常昂貴，但Mathematica已經實現了很多相似功能！所以我想象每個快捷方式可能 – user1063646

@user順便說一句，歡迎來到StackOverflow。你用上面顯示的「重複」來測試表單嗎？另外，如果不瞭解數據，就很難優化解決方案。如果你想要一個非常普遍和靈活的解決方案，可能很難打敗我上面展示的形式。序列總是一樣長嗎？所有相同類型的列表中的元素（float，integer等）？ –

@ user1063646不知道有關精確比較測試的任何信息，我所看到的唯一解決方案就是測試所有可能性（選擇所有子序列並對其進行比較）。這就是Mathematica使用模式匹配非常容易。但顯然這很慢。 **另外：**請在原始問題中添加校驗碼，以便每個人都可以輕鬆看到它們。 – Szabolcs

在列表中查找相同或相似的序列

回答

相關問題