0

上下文 - 开发算法以确定潮流网络中的回路流。

问题：

我有一个列表列表，每个列表代表通过我的算法确定的网络中的一个循环。不幸的是，该算法还将拾取反向重复。

IE

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 的答案，因为它提供了创建解决方案所需的密钥

4

3 回答 3

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

现在您知道如果两个列表相等，它们必须在列表中相邻，您可以使用 enumerate 将其拉出：

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)

如果您的（子）列表严格增加或严格减少，这将变得更加简单。

lists = list(set( tuple(sorted(x)) for x in your_list_of_lists ) )
于 2012-08-22T23:54:06.460 回答
0 
[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]or [-3,1,2]），那么您需要将它们视为等效项链

有很多方法可以规范化项链。上述方法效率较低，因为我们不关心直接规范化项链：我们只是将整个等价类视为规范元素，将每个循环(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)

旋转类似于在python中移动列表但产生元组的有效方法

于 2012-08-23T00:45:02.227 回答
0

如果您在两个方向上都有，我看不出它们如何等效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)])
于 2012-08-23T00:49:12.987 回答