從python列表中刪除類似但不相同的列表

Question

我正在識別方向圖中的循環。我的函數返回一個列表，它存儲所有找到的循環中的節點。

例如，在其中節點被連接這樣的曲線圖：

(1,2)(2,3)(3,4)(3,5)(5,2) 

一個環路以2發現 - 3 - 5，以便該函數將返回：

[[2,3,5]] 

在某些情況在那裏有多個迴路會返回類似的東西：

[[2,3,4][6,7,8,9]] 

這很好，但如果它e爲一圖表的多個開始點，這在不同的點加入到同一個環，如在圖中：

(1,2)(2,3)(3,4)(3,5)(5,2)(6,3) 

兩個節點1和6連接在不同的點在同一環，其將返回：

[[2,3,5][3,5,2]] 

所以這裏有兩個相同的循環，它們不是相同的列表。我想識別這種重複並刪除除了一個之外的所有內容（哪個並不重要）。

注意，可能存在有多個循環的情況下，其中一個是重複的，比如：我試圖尋找到itertools

[[2,3,5][3,5,2][7,8,9,6]] 

：

loops.sort() 
list(loops for loops,_ in itertools.groupby(loops)) 

但是這沒有幫助，而且我無法100％確定這是否合適。有任何想法嗎？我在Python 2.4上。謝謝你的幫助。

Answer 1

如果你只關心每個迴路的元素，而不是命令，我會通過排序它規範化每個循環，然後乘組：

>>> loops = [[2,3,5],[3,5,2],[7,8,9,6]] 
>>> set(tuple(sorted(loop)) for loop in loops) 
set([(2, 3, 5), (6, 7, 8, 9)]) 

爲了使用set這裏你需要轉換爲元組。你可以將元組轉換回列表，或者將最終的集合轉換回列表（甚至可以使用sorted來獲得規範的順序），但是實際上你是否需要依賴於你將要做的事情。

如果你需要保存路徑順序，我會以不同的方式規範化：

def rotated(l, n): 
    return l[n:] + l[:n] 

def canonicalize(l): 
    m = min(l) 
    where = l.index(m) 
    return rotated(l, where) 

然後

>>> loops = [[2,5,3], [5,3,2], [7,8,6,9]] 
>>> set(tuple(canonicalize(loop)) for loop in loops) 
set([(2, 5, 3), (6, 9, 7, 8)]) 

[編輯：請注意，這個簡單的規範化只能如果每個頂點只能在路徑中訪問一次。]

Answer 2

您可以在每個列表中輸入set。如果兩組相等，那麼你有一個重複的循環。儘管如此，你正在失去循環中的節點的順序，但是這對你有影響嗎？

Answer 3

首先，你需要定義類似的是什麼，因爲它比強set：

def is_similar(X,Y): 
    n = len(X) 
    return len(Y) == n and any(all(X[i] == Y[(i+j)%n] 
            for i in range(n)) 
           for j in range(1,n)) #the 1 here so that identical lists are not similar 

的區別如路徑（1,2,3,4）重要的是不同從路徑（1,3,2,4），它們不對應相同的循環。

def remove_similars(L): 
    new_L = [] 
    for item in L: 
     if not any(is_similar(item, l) for l in new_L): 
      new_L.append(item) 
    return new_L