[Tutor] A bit long, but would appreciate anyone's help, if time permits!

[Brian van den Broek]

Hee-Seng Kye said unto the world upon 23/07/2004 10:24:
> Hi.  I have a question that requires a bit of explanation.  I would 
> highly appreciate it if anyone could read this and offer any 
> suggestions, whenever time permits.
> 
> I'm trying to write a program that 1) gives all possible rotations of an 
> ordered list, 2) chooses the ordering that has the smallest difference 
> from first to last element of the rotation, and 3) continues to compare 
> the difference from first to second-to-last element, and so on, if there 
> was a tie in step 2.
> 
> The following is the output of a function I wrote.  The first 6 lines 
> are all possible rotations of [0,1,3,6,7,10], and this takes care of 
> step 1 mentioned above.  The last line provides the differences (mod 
> 12).  If the last line were denoted as r, r[0] lists the differences 
> from first to last element of each rotation (p0 through p5), r[1] the 
> differences from first to second-to-last element, and so on.
> 
>  >>> from normal import normal
>  >>> normal([0,1,3,6,7,10])
> [0, 1, 3, 6, 7, 10]    #p0
> [1, 3, 6, 7, 10, 0]    #p1
> [3, 6, 7, 10, 0, 1]    #p2
> [6, 7, 10, 0, 1, 3]    #p3
> [7, 10, 0, 1, 3, 6]    #p4
> [10, 0, 1, 3, 6, 7]    #p5
> 
> [[10, 11, 10, 9, 11, 9], [7, 9, 9, 7, 8, 8], [6, 6, 7, 6, 6, 5], [3, 5, 
> 4, 4, 5, 3], [1, 2, 3, 1, 3, 2]]     #r
> 
> Here is my question.  I'm having trouble realizing step 2 (and 3, if 
> necessary).  In the above case, the smallest number in r[0] is 9, which 
> is present in both r[0][3] and r[0][5].  This means that p3 and p5 and 
> only p3 and p5 need to be further compared.  r[1][3] is 7, and r[1][5] 
> is 8, so the comparison ends here, and the final result I'm looking for 
> is p3, [6,7,10,0,1,3] (the final 'n' value for 'pn' corresponds to the 
> final 'y' value for 'r[x][y]').
> 
> How would I find the smallest values of a list r[0], take only those 
> values (r[0][3] and r[0][5]) for further comparison (r[1][3] and 
> r[1][5]), and finally print a p3?
> 
> Thanks again for reading this.  If there is anything unclear, please let 
> me know.
> 
> Best,
> Kye
> 
> My code begins here:
> #normal.py
> def normal(s):
>     s.sort()
>     r = []
>     q = []
>     v = []
> 
>     for x in range(0, len(s)):
>         k = s[x:]+s[0:x]
>         r.append(k)
> 
>     for y in range(0, len(s)):
>         print r[y], '\t'
>         d = []
>         for yy in range(len(s)-1, 0, -1):
>             w = (r[y][yy]-r[y][0])%12
>             d.append(w)
>         q.append(d)
> 
>     for z in range(0, len(s)-1):
>         d = []
>         for zz in range(0, len(s)):
>             w = q[zz][z]
>             d.append(w)
>         v.append(d)
>     print '\n', v

Hi Kye,

I may not have understood your problem, but given your list of lists, I 
took you to want the one that has the least difference between first and 
last element to be selected, moving in one element on each end to break ties.

Why I think I may have misunderstood you is that you are doing something 
with arithmetic mod 12 and end up considering [6, 7, 10, 0, 1, 3] and [10, 
0, 1, 3, 6, 7] (your p3 and p5 from above) as the candidate "least 
elements". But from the description, I would have thought it was [1, 3, 6, 
7, 10, 0] (your  p1) that should be "least".

At any rate, for my understanding of your problem, I've written a (very 
lightly tested) way to do it. It takes your lists of lists as given, and 
then sorts them by the method I understood you to want. If it doesn't 
solve exactly your issue, perhaps it will serve as a start :-)

The idea is to replace your generation of your list r with a use of the 
sort method and a custom cmp() function.

Two warnings:
as I said, lightly tested.
I am no python expert! So my code shouldn't be seen as a model to follow. ;-)

The code:

Python 2.3.4 (#53, May 25 2004, 21:17:02) [MSC v.1200 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.

     ****************************************************************
     Personal firewall software may warn about the connection IDLE
     makes to its subprocess using this computer's internal loopback
     interface.  This connection is not visible on any external
     interface and no data is sent to or received from the Internet.
     ****************************************************************

IDLE 1.0.3
 >>> data = [[0, 1, 3, 6, 7, 10],
         [1, 3, 6, 7, 10, 0],
         [3, 6, 7, 10, 0, 1],
         [6, 7, 10, 0, 1, 3],
         [7, 10, 0, 1, 3, 6],
         [10, 0, 1, 3, 6, 7] ]
 >>> def special_cmp(first, second):
     upper_bound = (len(first) - 1) / 2
     level_count = 0
     comparison = 0
     while level_count <= upper_bound and comparison == 0:
         comparison = cmp(abs(first[level_count] - first[(-1 - level_count)]),
                          abs(second[level_count] - second[(-1 - 
level_count)]))
         level_count = level_count + 1
     return comparison

 >>> data.sort(special_cmp)
 >>> for d in data:
     print d, "Difference between first and last = %i" %(abs(d[0] - d[-1]))


[1, 3, 6, 7, 10, 0] Difference between first and last = 1
[7, 10, 0, 1, 3, 6] Difference between first and last = 1
[3, 6, 7, 10, 0, 1] Difference between first and last = 2
[10, 0, 1, 3, 6, 7] Difference between first and last = 3
[6, 7, 10, 0, 1, 3] Difference between first and last = 3
[0, 1, 3, 6, 7, 10] Difference between first and last = 10
 >>>

I hope that helps. If you'd like more detail as to how/why this works, ask ;-)

Best,

Brian vdB