通過唯一反轉的絕對條件對列表進行排序列表

Question

上下文 - 用於確定潮流網絡中環路流的開發算法。

問題：

我有一個列表的列表，每個列表表示通過我的算法來確定網絡中的循環。不幸的是，該算法也將挑選出相反的副本。

即

L1 = [a, b, c, -d, -a] 

L2 = [a, d, c, -b, -a] 

（請注意，C必須不爲負，這是正確的，由於作爲寫入網絡的結構和定義的流程）

現在這兩個循環是等價的，只是遵循整個網絡的逆向結構。

我希望保留L1，同時丟棄列表中的L2。 因此，如果我有6個循環的列表，其中3個是反向重複的，我希望保留所有三個循環。

此外，循環不必遵循上面指定的格式。它可以更短，更長，並且標誌結構（例如pos pos pos neg neg）不會在所有情況下發生。

我一直試圖通過顛倒列表和比較絕對值來對此進行排序。

我完全難住，任何援助將不勝感激。

根據mgibson提供的一些代碼，我可以創建以下內容。

def Check_Dup(Loops): 
    Act = [] 
    while Loops: 
     L = Loops.pop() 
     Act.append(L) 
     Loops = Popper(Loops, L) 
    return Act 

def Popper(Loops, L): 
    for loop in Loops: 
     Rev = loop[::-1] 
     if all (abs(x) == abs(y) for x, y in zip(loop_check, Rev)): 
      Loops.remove(loop) 
    return Loops 

此代碼應該運行，直到沒有剩下的循環每次丟棄重複。我接受mgibsons的答案，因爲它提供了必要的密鑰創建解決方案

Answer 1

我不知道我明白你的問題，但扭轉了名單很簡單：

a = [1,2] 
a_rev = a[::-1] #new list -- if you just want an iterator, reversed(a) also works. 

比較的絕對值a和a_rev：

all(abs(x) == abs(y) for x,y in zip(a,a_rev)) 

這可以簡化爲：

all(abs(x) == abs(y) for x,y in zip(a,reversed(a))) 

現在

，爲了使這一儘可能高效，我會先根據絕對值數組進行排序：

your_list_of_lists.sort(key = lambda x : map(abs,x)) 

現在你知道，如果兩個列表都將是平等的，他們必須是相鄰的列表，你可以只拉了這一點用列舉：

def cmp_list(x,y): 
    return True if x == y else all(abs(a) == abs(b) for a,b in zip(a,b)) 

duplicate_idx = [ idx for idx,val in enumerate(your_list_of_lists[1:]) 
        if cmp_list(val,your_list_of_lists[idx]) ] 

#now remove duplicates: 
for idx in reversed(duplicate_idx): 
    _ = your_list_of_lists.pop(idx) 

---

如果你的（子）列表要麼嚴格遞增或嚴格遞減，這成爲MUCH簡單。

lists = list(set(tuple(sorted(x)) for x in your_list_of_lists)) 

Answer 2

[pair[0] for pair in frozenset(sorted((c,negReversed(c))) for c in cycles)] 

其中：

def negReversed(list): 
    return tuple(-x for x in list[::-1]) 

，並在那裏cycles必須是元組。

這需要每個循環，計算其重複，並對它們進行排序（將它們放在一對具有相同等級的對中）。設置frozenset(...)獨一無二的重複。然後您提取的規範元素（在這種情況下，我隨意選了它是pair[0])。

---

請記住，你的算法可能會返回週期在任意的地方開始。如果是這樣的話（即你的算法可能會返回要麼[1,2,-3]或[-3,1,2]），那麼你就需要考慮這些等同necklaces

有很多方法來規範化項鍊上面的方法是低效率的，因爲我們不關心直接的進行規範化項鍊。我們只是將整個等價類視爲c通過將每個週期(a,b,c,d,e)轉換爲{(a,b,c,d,e), (e,a,b,c,d), (d,e,a,b,c), (c,d,e,a,b), (b,c,d,e,a)}。在你的情況下，因爲你認爲消極是相同的，你會把每個週期變成{(a,b,c,d,e), (e,a,b,c,d), (d,e,a,b,c), (c,d,e,a,b), (b,c,d,e,a), (-a,-b,-c,-d,-e), (-e,-a,-b,-c,-d), (-d,-e,-a,-b,-c), (-c,-d,-e,-a,-b), (-b,-c,-d,-e,-a)}。確保使用frozenset性能，如set不是可哈希：

eqClass.pop() for eqClass in {frozenset(eqClass(c)) for c in cycles} 

其中：

def eqClass(cycle): 
    for rotation in rotations(cycle): 
     yield rotation 
     yield (-x for x in rotation) 

，其中旋轉是一樣的東西Efficient way to shift a list in python而是生成一個元組

Answer 3

我怎麼沒看到如果您在兩個方向上都有c，則它們可以相當 - 其中一個必須是-c

>>> a,b,c,d = range(1,5) 
>>> L1 = [a, b, c, -d, -a] 
>>> L2 = [a, d, -c, -b, -a] 
>>> L1 == [-x for x in reversed(L2)] 
True 

現在你可以編寫一個函數來這兩個環路塌陷成一個單一的價值

>>> def normalise(loop): 
...  return min(loop, [-x for x in reversed(L2)]) 
... 
>>> normalise(L1) 
[1, 2, 3, -4, -1] 
>>> normalise(L2) 
[1, 2, 3, -4, -1] 

消除重複的一個好方法是使用一組，我們只需要在列表轉換成元組

>>> L=[L1, L2] 
>>> set(tuple(normalise(loop)) for loop in L) 
set([(1, 2, 3, -4, -1)])