遞歸刪除列表中的相鄰副本

我擡起頭，發現一個很接近的例子，但在這個鏈接中找到的答案：Remove adjacent duplicate elements from a list將不會運行這個問題的測試用例。所以這是我到目前爲止有：遞歸刪除列表中的相鄰副本

def remove_dups(thelist): 
    """Returns: a COPY of thelist with adjacent duplicates removed. 

    Example: for thelist = [1,2,2,3,3,3,4,5,1,1,1], 
    the answer is [1,2,3,4,5,1] 

    Precondition: thelist is a list of ints""" 
    i = 1 
    if len(thelist) == 0: 
     return [] 
    elif len(thelist) == 1: 
     return thelist 
    elif thelist[i] == thelist[i-1]: 
     del thelist[i] 
    return remove_dups(thelist[i:]) 


def test_remove_dups(): 
    assert_equals([], remove_dups([])) 
    assert_equals([3], remove_dups([3,3])) 
    assert_equals([4], remove_dups([4])) 
    assert_equals([5], remove_dups([5, 5])) 
    assert_equals([1,2,3,4,5,1], remove_dups([1,2,2,3,3,3,4,5,1,1,1])) 

# test for whether the code is really returning a copy of the original list 
    mylist = [3] 
    assert_equals(False, mylist is remove_dups(mylist))

編輯，同時我也明白，上面用itertools.groupby將工作掛鉤接受的答案，我想會不會教我什麼是錯我的代碼&並會如果我從itertools中導入了grouby，就會擊敗練習的目的。

來源

2014-03-26 Dave Lee

它必須是遞歸的嗎？你能排序它，然後迭代它嗎？ – AndyG

我會認爲排序是錯誤的，否則你只是做排序（設置（列表）） –

@andyG是的，它必須是遞歸的 –

from itertools import groupby 

def remove_dups(lst): 
    return [k for k,items in groupby(lst)]

如果你真的想要一個遞歸解決方案，我建議像

def remove_dups(lst): 
    if lst: 
     firstval = lst[0] 

     # find lowest index of val != firstval 
     for index, value in enumerate(lst): 
      if value != firstval: 
       return [firstval] + remove_dups(lst[index:]) 

     # no such value found 
     return [firstval] 
    else: 
     # empty list 
     return []

來源

2014-03-26 20:11:15

你的斷言失敗，因爲在

return thelist

在評論中指定要返回相同的列表，而不是一個副本。

嘗試：

return thelist[:]

來源

2014-03-26 20:05:15 Hyperboreus

你是對的，但那不會不會改變我最終的結果 - 我想我需要改變第一組代碼的最後三行。 –

當使用遞歸處理列表是大部分時間的問題返回一個子列表或該列表的一部分。這使終止案例測試一個空的列表。然後你有兩種情況：

電流值是從我們看到的，所以我們要保持它的
當前值是一樣的，最後一個我們看到，所以我們放棄它的最後一個不同並繼續迭代值的「休息」。在此代碼

哪個翻譯：

l = [1,2,2,3,3,3,4,5,1,1,1] 

def dedup(values, uniq): 
    # The list of values is empty our work here is done 
    if not values: 
    return uniq 
    # We add a value in 'uniq' for two reasons: 
    # 1/ it is empty and we need to start somewhere 
    # 2/ it is different from the last value that was added 
    if not uniq or values[0] != uniq[-1]: 
    uniq.append(values.pop(0)) 
    return dedup(values, uniq) 
    # We just added the exact same value so we remove it from 'values' and 
    # move to the next iteration 
    return dedup(values[1:], uniq) 

print dedup(l, []) # output: [1, 2, 3, 4, 5, 1]

來源

2014-03-26 20:27:39 bvidal

謝謝你的深入解釋 - 我很欣賞線條間的意見。 –

問題是在你return語句，

要返回

return remove_dups(thelist[i:])

輸出會一直持續列表的n個單個元素

喜歡上面很快，

print remove_dups([1,2,2,3,3,3,4,5,1,1,1]) 
>>> [1] #as your desired is [1,2,3,4,5,1]

它最終返回單個元素的列表，因爲它不考慮Oth元素。

這裏是遞歸解決方案。

def remove_dups(lst): 
    if len(lst)>1: 

     if lst[0] != lst[1]: 
      return [lst[0]] + remove_dups(lst[1:]) 

     del lst[1] 
     return remove_dups(lst) 
    else: 
     return lst

來源

2014-03-26 20:34:56 Roshan

你是對的！我一直只獲得一個價值。謝謝。 –

我已編輯解決方案的答案，您可以查看它。我認爲它更好的解決方案。 – Roshan

遞歸刪除列表中的相鄰副本

回答

相關問題