Challenge #8: Order this list
Document Actions
Sometimes, you need an arbitrary, but specified order...
Given a list in a specific order, can you take a second list of the same type, and order it in respect to the first list. i.e.
sort this list:
[u', 'd', 'h', 'j', 'm', 'e', 'p', 'z', 'g', 'u', 'e', 'g']
according to this sorting scheme:
['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l']
That is, take the first list and rearrange it so that its letters are in the same order as those in the second list. You'll have to account for the fact that the two lists don't overlap perfectly; the first one doesn't have all the letters in the second one, and more distressingly, the second list -- the one that's providing the sort key -- doesn't contain all the letters represented in the first list. Handle those extras by sticking them at the end of the sorted list, preserving their order.
This challenge brought to you by Ross, with write-up by Jenn and some sort of involvement by Stephan.
An extra tweak: move the 'unknown' values to the _front_ of the list, preserving their relative order. For my soultion, this is actually easier. I can think of a use involving UIs for folksonomies w/ tags, perhaps. (reedstrm added)
sort this list:
[u', 'd', 'h', 'j', 'm', 'e', 'p', 'z', 'g', 'u', 'e', 'g']
according to this sorting scheme:
['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l']
That is, take the first list and rearrange it so that its letters are in the same order as those in the second list. You'll have to account for the fact that the two lists don't overlap perfectly; the first one doesn't have all the letters in the second one, and more distressingly, the second list -- the one that's providing the sort key -- doesn't contain all the letters represented in the first list. Handle those extras by sticking them at the end of the sorted list, preserving their order.
This challenge brought to you by Ross, with write-up by Jenn and some sort of involvement by Stephan.
An extra tweak: move the 'unknown' values to the _front_ of the list, preserving their relative order. For my soultion, this is actually easier. I can think of a use involving UIs for folksonomies w/ tags, perhaps. (reedstrm added)
Re: Challenge #8: Order this list
Posted by
jenn
at
2006-09-12 15:10
For the record, Stefan's contribution was...having the problem in the first place! So this is a real-world one. I hear it rumored that Ross came up with a one-liner solution for Stefan's actual case. Extra credit if you can do the same.
Re: Challenge #8: Order this list
Posted by
reedstrm
at
2006-09-13 10:26
I can't remember the actual real-world reason (something to do with sorting xml nodes, probably) The one-liner-ness of my solution is because I havea bad case of one-liner disease, and I put way too much python code into TAL templates, where one-liners are sometimes the only thing that fits. (Yeah, I should refactor more)
Re: Re: Challenge #8: Order this list
Posted by
cbearden
at
2006-09-14 15:20
While one-liners are not always the optimal solution for production code, it does strike me as a useful mental exercise to strive for a one-liner solution to problems like this. I'm intrigued enough about your solution to spend some time at home (maybe) trying to find my own one-liner. Then I'll have a look at your solution.
http://rhaptos.org/Members/jenn/pychallenges/pychallenge8
"order the list elements in l2 with the same relative order as they have in l1. Extra elements move to the end, without change their relative order"
>> l1
[1, 3, 4, 6, 7]
>>> l2
[0, 4, 'c', 3, 6, 7, 8, 'a', 'b']
>>> l2.sort(lambda x,y: (l1.count(x) and (l1.index(x)+1) or (len(l1)+1))-(l1.count(y) and (l1.index(y)+1) or (len(l1)+1)))
>>> l2
[3, 4, 6, 7, 0, 'c', 8, 'a', 'b']
What this teaches is passing a comparison function to sort, the use of list index, list count, and the "a and b or c" pythonic idiom. In general, cmp functions are supposed to return -1 for x < y, 0 for x = y, and 1 for x > y. In reality, anything negative is treated as -1, anything positive as 1. So, we can use the difference of the index positions as the cmp function. In additon, in order to avoid ValueErrors for items in list 2 not in list 1, we have to use the count() method, to substitute a value just beyond the end of the list. We need to add 1 to all the index values, or the first item in l1 gets treated as not present, since 1 and 0 is false. We can see if we add a '1' to l2:
>>> l2=[1,0, 4, 'c', 3, 6, 7, 8, 'a', 'b']
>>> l2.sort(lambda x,y: (l1.count(x) and (l1.index(x)) or (len(l1)))-(l1.count(y) and (l1.index(y)) or (len(l1))))
>>> l2
[3, 4, 6, 7, 1, 0, 'c', 8, 'a', 'b']
>>> l2.sort(lambda x,y: (l1.count(x) and (l1.index(x)+1) or (len(l1)+1))-(l1.count(y) and (l1.index(y)+1) or (len(l1)+1)))
>>> l2
[1, 3, 4, 6, 7, 0, 'c', 8, 'a', 'b']