Python .sort() not working as expected

Question

Tackling a few puzzle problems on a quiet Saturday night (wooohoo... not) and am struggling with sort(). The results aren't quite what I expect. The program iterates through every combination from 100 - 999 and checks if the product is a palindome. If it is, append to the list. I need the list sorted :D Here's my program:

list = [] #list of numbers

for x in xrange(100,1000): #loops for first value of combination
  for y in xrange(x,1000): #and 2nd value
    mult = x*y
    reversed = str(mult)[::-1] #reverses the number
    if (reversed == str(mult)):
      list.append(reversed)

list.sort()
print list[:10]

which nets:

['101101', '10201', '102201', '102201', '105501', '105501', '106601', '108801',
'108801', '110011']

Clearly index 0 is larger then 1. Any idea what's going on? I have a feeling it's got something to do with trailing/leading zeroes, but I had a quick look and I can't see the problem.

Bonus points if you know where the puzzle comes from :P

Answer 1

You are sorting strings, not numbers. '101101' < '10201' because '1' < '2'. Change list.append(reversed) to list.append(int(reversed)) and it will work (or use a different sorting function).

Answer 2

Sort is doing its job. If you intended to store integers in the list, take Lukáš advice. You can also tell sort how to sort, for example by making ints:

list.sort(key=int)

the key parameter takes a function that calculates an item to take the list object's place in all comparisons. An integer will compare numerically as you expect.

(By the way, list is a really bad variable name, as you override the builtin list() type!)