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

You have your numbers stored as strings, so python is sorting them accordingly. So: '101x' comes before '102x' (the same way that 'abcd' will come before 'az').

Answer 3

No, it is sorting properly, just that it is sorting lexographically and you want numeric sorting... so remove the "str()"

Answer 4

You're sorting strings, not numbers. Strings compare left-to-right.

Answer 5

Your list contains strings so it is sorting them alphabetically - try converting the list to integers and then do the sort.

Answer 6

The comparator operator is treating your input as strings instead of integers. In string comparsion 2 as the 3rd letter is lexically greater than 1. reversed = str(mult)[::-1]

Answer 7

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

Answer 8

No need to convert to int. mult already is an int and as you have checked it is a palindrome it will look the same as reversed, so just:

list.append(mult)