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

Brian van den Broek bvande at po-box.mcgill.ca
Fri Jul 23 18:23:41 CEST 2004

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

More information about the Tutor mailing list