0

I'm trying to figure out a way to check if order exists in a sequence of elements. For example:

orderExists = [
    ['a','c','d','e'],['b','d','f'],['a','b','c','e']
]
orderViolation = [
    ['a','c','d','e'],['b','d','f'],['a','e','c','b']
]

Order exists because the valid sequence should look like a,b,c,d,e,f. In sublists the elements may be absent. For example in orderExists[0] = ['a','c','d','e'] b and f are absent but as long as c comes after a and is before d order is respected.

Order is violated because in orderViolation[2] = ['a','e','c','b'] e should not be before c.

Also this is a test case, i don't know the valid sequence, the only thing that i have is a list of sublists as in the example above.

Is there any effective way to find out if there order exists or not?

NOTE: The sublists do not contain only elements in alphabetical order.

For Example: New York --> Los Angeles --> Chicago

orderExists = [
        ['Los Angeles', 'Chicago'],
        ['New York','Los Angeles'],
        ['New York','Chicacgo']
    ]
alcheringa
  • 33
  • 3
  • 1
    Does this answer your question? [Pythonic way to check if a list is sorted or not](https://stackoverflow.com/questions/3755136/pythonic-way-to-check-if-a-list-is-sorted-or-not) – mkrieger1 Jul 28 '21 at 22:00

2 Answers2

0

You can create a masking list that contains whether the lists inside the lists are ordered or not, by comparing each inner list with their sorted version.

>>> [x==sorted(x) for x in orderExists]
[True, True, True]

>>> [x==sorted(x) for x in orderViolation]
[True, True, False]

Or, you can just compare if each item is greater than the previous inside each sub-lists:

>>> [all(x[i+1]>x[i] for i in range(len(x)-1)) for x in orderViolation]
[True, True, False]
ThePyGuy
  • 17,779
  • 5
  • 18
  • 45
  • Thank you for your reply. This solution is great for the test case that i provided, but if i have a list of cities and each sublist is a version of order in which they were visited. For example: New York --> Los Angeles --> Chicago `orderExists = [ ['Los Angeles', 'Chicago'], ['New York','Los Angeles'], ['New York','Chicacgo'] ]` – alcheringa Jul 28 '21 at 22:40
  • 1
    @alcheringa Please edit your question and include test cases representative of your actual problem. – Woodford Jul 28 '21 at 23:04
0

Solution:

import itertools

def compareOrders(l1, l2):
    
    aa = [elem for elem in l1 if elem in l2]
    bb = [elem for elem in l2 if elem in l1]

    return aa == bb


orderExists = [
        ['Los Angeles', 'Chicago'],
        ['New York','Los Angeles'],
        ['New York','Chicacgo']
    ]


agreement = []

for a, b in itertools.combinations(orderExists, 2):
    if compareOrders(a, b):
        agreement.append(True)
    else: agreement.append(False)

if all(agreement): print('ORDER EXISTS')
else: print('ORDER VIOLATION')
alcheringa
  • 33
  • 3