Sort list of lists by unique reversed absolute condition

Question

Context - developing algorithm to determine loop flows in a power flow network.

Issue:

I have a list of lists, each list represents a loop within the network determined via my algorithm. Unfortunately, the algorithm will also pick up the reversed duplicates.

i.e.

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

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

(Please note that c should not be negative, it is correct as written due to the structure of the network and defined flows)

Now these two loops are equivalent, simply following the reverse structure throughout the network.

I wish to retain L1, whilst discarding L2 from the list of lists. Thus if I have a list of 6 loops, of which 3 are reversed duplicates I wish to retain all three.

Additionally, The loop does not have to follow the format specified above. It can be shorter, longer, and the sign structure (e.g. pos pos pos neg neg) will not occur in all instances.

I have been attempting to sort this by reversing the list and comparing the absolute values.

I am completely stumped and any assistance would be appreciated.

Based upon some of the code provided by mgibson I was able to create the following.

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

This code should run until there are no loops left discarding the duplicates each time. I'm accepting mgibsons answers as it provided the necessary keys to create the solution

Answer 1

I'm not sure I get your question, but reversing a list is easy:

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

To compare the absolute values of a and a_rev:

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

which can be simplified to:

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

Now, in order to make this as efficient as possible, I would first sort the arrays based on the absolute value:

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

Now you know that if two lists are going to be equal, they have to be adjacent in the list and you can just pull that out using 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)

---

If your (sub) lists are either strictly increasing or strictly decreasing, this becomes MUCH simpler.

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

Where:

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

and where cycles must be tuples.

This takes each cycle, computes its duplicate, and sorts them (putting them in a pair that are canonically equivalent). The set frozenset(...) uniquifies any duplicates. Then you extract the canonical element (in this case I arbitrarily chose it to be pair[0]).

---

Keep in mind that your algorithm might be returning cycles starting in arbitrary places. If this is the case (i.e. your algorithm might return either [1,2,-3] or [-3,1,2]), then you need to consider these as equivalent necklaces

There are many ways to canonicalize necklaces. The above way is less efficient because we don't care about canonicalizing the necklace directly: we just treat the entire equivalence class as the canonical element, by turning each cycle (a,b,c,d,e) into {(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)}. In your case since you consider negatives to be equivalent, you would turn each cycle into {(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)}. Make sure to use frozenset for performance, as set is not hashable:

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

where:

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

where rotation is something like Efficient way to shift a list in python but yields a tuple

Answer 3

I don't see how they can be equivalent if you have c in both directions - one of them must be -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

now you can write a function to collapse those two loops into a single value

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

A good way to eliminate duplicates is to use a set, we just need to convert the lists to tuples

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