通过唯一反转的绝对条件对列表进行排序列表

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)])