Hi, i'm trying to take the last list from a list of lists, use that as a start point, then iterate through the list of lists and find the closest match, then use that matched list as a base and iterate through the remaining lists for the closest match to that list,then use that list as a base, and so on. Reordering the original list of lists.

SequenceMatcher seems to do the job, to get the first closest match.
How could i change the code so it would do what is required from within a function, or indeed in any other way.

I am new to both Python and this forum, as you can probably tell from my code. Here it is.

``````List1=[[6,5,4],[2,3,5],[1,2,3],[3,4,5],[1,2,3,4]]
print List1
List2=[]
LastvaL=List1.pop()
List2.append(LastvaL)
from difflib import SequenceMatcher
i=0
s= SequenceMatcher()
s.set_seq2(LastvaL)
s.set_seq1(List1[i])
hoLder=[]
previous=0
print "previous",previous
for item in List1[0:-1]:
print item
s.set_seq1(List1[i])
s.ratio()
current=s.ratio()
if current>previous:
print "current",current,"previous",previous
previous=current
hoLder=[]
hoLder.append(List1[i])
print "ratio",s.ratio()
i=i+1
List2.append(hoLder)
print List2``````

I have included an example list in this code.
I would like to put this code or similar in a function because my list has a hundred lists in it, but I dont know how to do that.
Any help or ideas would be greatly appreciated. Thank you.

2
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by Gribouillis

Here is a code which uses a helper class and a few functions to implement your algorithm. Tell me if it works as you expect

``````# orderer.py
# tested with python 2.6 and 3.1
from difflib import SequenceMatcher

class Orderer(object):
"Helper class for the ordering algorithm"

def __init__(self):
self.matcher = SequenceMatcher()

def order(self, alist):
"orders the list in place"
if not alist:
return
alist[0], alist[-1] = alist[-1], alist[0] # swap first and last elements
self.rank = 1 # self.rank is the index where unordered elements start
while self.rank < len(alist): # while there are unordered elements
self.matcher.set_seq1(alist[self.rank-1]) # the last sublist found
# find the best match
index, sublist = max(enumerate(alist[self.rank:], start = self.rank), key = self.key)
alist[self.rank], alist[index] = alist[index], alist[self.rank]
self.rank += 1

def key(self, item):
"score function for the call to 'max'. The score of an item is its 'ratio'"
index, sublist = item
self.matcher.set_seq2(sublist)
return self.matcher.ratio()

def order(alist):
"Order a list of lists in place with difflib"
Orderer().order(alist)

def ordered(alist):
"Return a new list of lists ordered with difflib"
other = list(alist)
order(other)
return other

if __name__ == "__main__":
my_list = [[6,5,4],[2,3,5],[1,2,3],[3,4,5],[1,2,3,4]]
print(str(my_list))
print(str(ordered(my_list)))

"""
My output --->
[[6, 5, 4], [2, 3, 5], [1, 2, 3], [3, 4, 5], [1, 2, 3, 4]]
[[1, 2, 3, 4], [1, 2, 3], [2, 3, 5], [3, 4, 5], [6, 5, 4]]
"""``````

Especially the comments, which help me understand what's going on and from which i am learning a lot.
Your solution does just what I wanted. Thanks very much.

A slight improvement of the previous code :)

``````# orderer.py
from difflib import SequenceMatcher
import sys
if sys.version_info < (3,):
range = xrange # if python 2, use xrange for speed

class Orderer(object):
"Helper class for the ordering algorithm"

def __init__(self):
self.matcher = SequenceMatcher()

def order(self, alist):
"orders the list in place"
if not alist:
return
self.alist = alist # reference used in the 'key' method
alist[0], alist[-1] = alist[-1], alist[0] # swap first and last elements
for rank in range(1, len(alist)):
# rank is the index of the first unordered element
self.matcher.set_seq1(alist[rank-1]) # the last sublist found
# find the best match among unordered elements
best = max(range(rank, len(alist)), key = self.key)
alist[rank], alist[best] = alist[best], alist[rank]
del self.alist # don't keep a reference to alist

def key(self, index):
"""score function for the call to 'max'.
The score of an item is its 'ratio'"""
self.matcher.set_seq2(self.alist[index])
return self.matcher.ratio()

def order(alist):
"Order a list of lists in place with difflib"
Orderer().order(alist)

def ordered(alist):
"Return a new list of lists ordered with difflib"
other = list(alist)
order(other)
return other

if __name__ == "__main__":
my_list = [[6,5,4],[2,3,5],[1,2,3],[3,4,5],[1,2,3,4]]
print(str(my_list))
print(str(ordered(my_list)))``````

Edited by Gribouillis: n/a

Last and ultimate version without class for python lovers

``````# orderer.py
from difflib import SequenceMatcher
import sys
if sys.version_info < (3,):
range = xrange

def order(alist):
"order(alist) -> alist: order a list in place with difflib"
n = len(alist)
if not n:
return alist

matcher = SequenceMatcher()

def score(index):
matcher.set_seq2(alist[index])
return matcher.ratio()

def swap(i, j):
alist[i], alist[j] = alist[j], alist[i]

swap(0, -1)
for i in range(1, n-1):
matcher.set_seq1(alist[i-1])
swap(i, max(range(i, n), key = score))
return alist

if __name__ == "__main__":
my_list = [[6,5,4],[2,3,5],[1,2,3],[3,4,5],[1,2,3,4]]
print(str(my_list))
print(str(order(list(my_list))))``````

Edited by Gribouillis: n/a