Logically sorting a list of lists

  • A+
Category:Languages

Take this list of lists:
[['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd'], ]
and flatten it to a single list, sorted depending on a value's neighbor(s):

  • the first sublist tells you that b comes before c
  • then a before c
  • b before a
  • and finally d after c

The overall ordering between sublists is consistent, meaning there won't be sublists like these: ['b','c'],['c','b']. So the result should be: ['b', 'a', 'c', 'd']

After a (long) while I came up with this ugly mess:

def get_order(_list):     order = _list[0]     for sublist in _list[1:]:         if not sublist:             continue         if len(sublist) == 1:             if sublist[0] not in order:                 order.append(sublist[0])             continue         new_order = order.copy()         for index, value in enumerate(sublist):             inserted = False             new_order_index = None             if value in new_order:                 new_order_index = new_order.index(value)                 new_order.remove(value)             for previous_value in sublist[:index][::-1]:                 if previous_value in new_order:                     insert_index = new_order.index(previous_value) + 1                     print('inserting', value, 'at position', insert_index, 'after', previous_value)                     new_order.insert(insert_index, value)                     inserted = True                     break             if inserted:                 continue             for next_value in sublist[index:]:                 if next_value in new_order:                     insert_index = new_order.index(next_value)                     print('inserting', value, 'at position', insert_index, 'before', next_value)                     new_order.insert(insert_index, value)                     inserted = True                     break             if inserted:                 continue             if new_order_index is None:                 print('appending', value)                 new_order.append(value)             else:                 print('leaving', value, 'at position', new_order_index)                 new_order.insert(new_order_index, value)         order = new_order     return order  if __name__ == '__main__':     test_list = [['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd'], ]     order = get_order(test_list)     #>>> inserting a at position 1 before c     #>>> inserting c at position 2 after a     #>>> inserting d at position 3 after c     #>>> inserting a at position 1 before c     #>>> inserting c at position 2 after a     #>>> inserting b at position 0 before a     #>>> inserting a at position 1 after b     print(order)     #>>> ['b', 'a', 'c', 'd'] 

It appears to do exactly as expected, but it is far from efficient (or elegant for that matter).
Are there any algorithms that can sort like that?
Or are there some pythonic tricks that would make this more efficient?

 


It is simpler with a compare function:

rules = [['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd']]  def compare(element1, element2):     for rule in rules:         if element1 in rule and element2 in rule:             if rule.index(element1) < rule.index(element2):                 return -1             else:                 return 1     else:         return 0  flattened = sorted(     set(element for sublist in rules for element in sublist),      cmp=compare ) print(flattened) 

results:

['b', 'a', 'c', 'd'] 

And if you do:

rules = [['b', 'c'], ['a', 'c'], ['b', 'a'], ['a', 'c', 'd'], ['a', 'e']] 

You get:

['b', 'a', 'c', 'e', 'd'] 

OBS: This works in python 2. In python 3 you should write the sorted line like this:

flattened = sorted(     set(element for sublist in rules for element in sublist),      key=functools.cmp_to_key(compare) ) 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: