簡單的遞歸剽竊探測器陣列

我在想一個非常簡單的剽竊探測器。爲了簡單起見，假設你將不得不在beignning兩個列表，每個都有一些字符串元素，例如：簡單的遞歸剽竊探測器陣列

l1 = [ "I","like","big","yellow","bananas" ] 
l2 = [ "I","like","yellow","bananas" ]

用戶還可以指定，每一個操作「成本」是多少，讓我們說：

DeletePrice = 10   #deleting word from one list 
InsertPrice = 1   #insterting a word to one list 
SubstitutePrice = 24  #substituing a word for another one

的任務是相匹配的列表和組合價格已經是最低的。有兩種明顯的方法來匹配這些數組，一種是從第一個數組中刪除「big」（這將花費10）或向第二個數組中插入一個單詞「big」（這將花費1）。該算法的答案應該是這樣1.

我在想，在一開始，我們應該找到的元素，不匹配，使用列表理解中：

def Plagiarism(l1,l2,dPrice,iPrice,sPrice): 
    not_matching_elements = [ [ x for x in l1 if x not in l2 ],[ x for x in l2 if x not in l1 ] ]

的 not_matching_elements 名單將給我們 [ [ big ],[] ] 並可能會幫助我們前進。但我無法想出一種方法來進一步開發該算法。謝謝。

來源

2016-03-02 TheTask1337

那麼是「請完成開發我的算法？」的問題。另外，如果您採取的第一步是找出差異，那麼下一步就不會使用差異來計算成本了嗎？ – Jacobr365

這個問題需要比我們提供的更多的幫助。我們喜歡幫助人們，但有時候這個人需要先閱讀一本有關該語言的書籍，在線文檔或詢問他們認識的人來幫助他們。一旦你更好地理解了這個話題，我們邀請你編輯這個問題並重新打開它。 – Prune

更重要的是，您在發佈之前在線上發現的剽竊算法有什麼問題？你在哪裏堅持選擇和實施其中之一？你開發了什麼替代方法？ – Prune

你描述的過程非常類似Levenshtein距離：

https://en.wikipedia.org/wiki/Levenshtein_distance

你只是想數組項，而不是字符。

你可以簡單地找到levensthein算法，並改變它，以滿足您的需求

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python

該算法甚至可能會爲陣列工作;）

編輯：這工作：

def levenshtein(s1, s2): 
    insertionCost=1 
    deletionCost=1 
    substitutionCost=1 

    if len(s1) < len(s2): 
     return levenshtein(s2, s1) 

    # len(s1) >= len(s2) 
    if len(s2) == 0: 
     return min(deletionCost,insertionCost)*len(s1) 

    previous_row = range(len(s2) + 1) 
    for i, c1 in enumerate(s1): 
     current_row = [i + 1] 
     for j, c2 in enumerate(s2): 
      insertions = previous_row[j + 1] + insertionCost # j+1 instead of j since previous_row and current_row are one character longer 
      deletions = current_row[j] + deletionCost  # than s2 
      substitutions = previous_row[j] + substitutionCost*(c1 != c2) 
      current_row.append(min(insertions, deletions, substitutions)) 
     previous_row = current_row 

    return previous_row[-1] 


#returns 2 
print(levenshtein(['abc','def','ghi'],['abc','ghi','e']))

來源

2016-03-02 20:53:11 JeD

非常感謝你，這工作像一個魅力 – TheTask1337

@TheTask1337沒有問題;） – JeD

簡單的遞歸剽竊探測器陣列

回答

相關問題