比較元素的順序列出

Question

我試圖寫一個返回True如果他們出現在lst1在lst1的元素出現在lst2在同一順序的功能，但不一定連續。

例如，

test([29, 5, 100], [20, 29, 30, 50, 5, 100])應該返回True。

test([25, 65, 40], [40, 25, 30, 65, 1, 100])應該返回False。

這是我到目前爲止有：

def test(lst1, lst2): 
    for i in range(len(lst1)-len(lst2)+1): 
     if lst2 == lst1[i:i+len(lst2)]: 
      return True 
    return False 

Answer 1

def test(lst1, lst2): 
    for x in lst2: 
     if x == lst1[0]: 
      del lst1[0] 
    return lst1 == [] 

應該工作。

Answer 2

此掃描列表和是一個不同的方法：

def test(lst1, lst2): 
    p2 = 0 
    length = len(lst2) 
    for e1 in lst1: 
     for p in range(p2, length): 
      if e1 == lst2[p]: 
       p2 = p 
       break 
     else: 
      return False  
    return True 

對於lst1每個元素它搜索列表2的子集用於它（p2和端部之間）。如果找到，則通過更新p2來限制搜索範圍。如果找不到，則返回False。如果找到lst1中的每個元素，則返回True。

Answer 3

遞歸，沒有重挫名單，沒有新的子列表，沒有早

def find_all(needle, haystack, npos=0, hpos=0): 
    if npos >= len(needle): 
    return True 
    try: 
    return find_all(needle, haystack, npos+1, haystack.index(needle[npos], hpos)+1) 
    except ValueError: 
    return False 


print find_all([1,3,5], [1,2,3,4,5,6,7]) # True 
print find_all([1,5,3], [1,2,3,4,5,6,7]) # False 

Answer 4

下面是使用由三聯給出index方法的迭代版本。我想這大概是做到這一點的最好辦法，因爲index應該比任何手工索引或迭代更快：

def test(lst1, lst2): 
    start = 0 
    try: 
     for item in lst1: 
      start = lst2.index(item, start) + 1 
    except ValueError: 
     return False 
    return True 

應該在Python比遞歸版本執行更好。它還在每次搜索後正確添加一個到開始點，以便在第一個列表中有重複時不會給出誤報。

以下是兩種解決方案，主要針對lst2而不是lst1進行迭代，但在其他方面類似於jedwards的版本。

首先是直接的，並使用索引，而只索引當你真正移動到不同的項目中lst1，而不是對每一個項目在lst2：

def test(lst1, lst2): 
    length, i, item = len(lst1), 0, lst1[0] 
    for x in lst2: 
     if x == item: 
      i += 1 
      if i == length: 
       return True 
      item = lst1[i] 
    return False 

第二種方法是使用手動遍歷所有lst1與next而不是索引：

def test(lst1, lst2): 
    it = iter(lst1) 
    try: 
     i = next(it) 
     for x in lst2: 
      if x == i: 
       i = next(it) 
    except StopIteration: 
     return True 
    return False 

兩者都是可能略有改善，因爲他們少做索引和有沒有必要建立一個range爲電子商務非常項目lst1。