SequenceMatch list of lists

[mwitu]

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.

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

[mwitu]

Thank you Gribouillis, for your reply and code.
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.

[Gribouillis]

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

[Gribouillis]

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