How to sort a list? NOT a newbie question.

[Grant Griffin]

In article <4jcgqtsvc9dc7or96alisr6rhcv776qhd1 at 4ax.com>, Tim says...
>
>mjbarber at ascc.artsci.wustl.edu (Michael James Barber) wrote:
>
>>All in Python 2.1.1:
>>
>>>>> l1 = [1, '1j', [1,'1j']]
>>>>> l1.sort()
>>>>> print l1
>>[1, [1, '1j'], '1j']
>>
>>>>> l2 = [1, 1j, [1,'1j']]
>>>>> l2.sort()
>>Traceback (most recent call last):
>>  File "<input>", line 1, in ?
>>TypeError: cannot compare complex numbers using <, <=, >, >=
>>
>>
>>This came up in the context of building the coefficients of polynomials 
>>from a list of roots.  If complex roots occur in complex conjugate pairs, 
>>then the resulting coefficients must be real, so I decided to cast the 
>>coefficients to floats in this case.  A straightforward test is to take 
>>the complex conjugate of each element of the list, then sort both lists 
>>and see if they are the same.  As is clear from the above, that definitely 
>>didn't work!  
>
>You can make this work if you can answer a couple of simple questions.  
>
>Which is greater:  3 or 3j?

3j: both have the same magnitude, but 3j has a greater phase (90 degrees as
opposed to 0).  So I'm gonna say 3j is greater.  (Does anybody care to fight me
to the death over that one <wink>?)

>Put these numbers in order:   3+0j  1+1j  1+2j  2+1j  2+2j   1+0j  0+3j

OK.  Here's an ordering based on comparing the inphase, then the quadrature
components:

   0+3j  1+0j  1+1j  1+2j  2+1j  2+2j  3+0j

Of course, other orderings are possible based on other comparison conventions.

I like to think of complex numbers as being "two-valued numbers" which can be
represented equivalently either in Cartesian form (x + jy) or polar form
(magnitude at phase--kindda like e-mail <wink>).  The concept of "equality" of
complex numbers is perfectly mathematically sensible, but the concept of "less
than", and "greater than" make sense only in terms of a complex number's two
component real values (either inphase/quadrature or magnitude/phase).

For the purposes of sorting, it is entirely sensible to use any convention for
comparison that compares one of the two real values individually, then breaks
ties using the other one.  Of course, you could do this in either Cartesian or
polar representation (assuming the phase has been normalized).  Those
conventions would have different--but consistent--results.

In Python, it is more expedient to do comparisons based on the Cartesian
representation since that is what Python uses internally to store complex
numbers.  However, the most generally useful method would be to compare first on
magnitude, then on phase (and assuming normalization of phase to the range of
+/- 180 degrees) would probably be .  (A complex number's magnitude is what we
generally think of as its "size", so a complex number with a bigger magnitude
seems to be "greater".)

Note that Python has something of an inconsistency in the fact that it happily
compares _different_ data types:

   >>> a=1
   >>> b=[0,2,3]
   >>> a>b
   0
   >>> c=[2,3,4]
   >>> a>c
   0
   >>> t=()
   >>> l=[]
   >>> t>l
   1

yet refuses to compare complex numbers of the _same_ type!:

  >>> c1=1+1j
  >>> c2=2+2j
   >>> cmp(c1,c2)
  Traceback (most recent call last):
     File "<stdin>", line 1, in ?
   TypeError: cannot compare complex numbers using <, <=, >, >=
   >>> c1<c1
   Traceback (most recent call last):
     File "<stdin>", line 1, in ?
   TypeError: cannot compare complex numbers using <, <=, >, >=

Presumably this is by design: perhaps Python doesn't want to mislead you that
these operations are mathematically meaningful when they aren't.  (BTW, neither
is comparing different data types, bug I guess you're supposed to figure that
one out yourself.)

For sorting, you could try comparing complex numbers based on their hashed
value:

   >>> hash(c1)
   1000004
   >>> hash(c2)
   2000008

Since the hashed values are integers, one can compare based on those.  Hashed
valued are not guaranteed to be unique (specifically, one can't uniquely squeeze
two floating-point valuess into a single integer), but for most practical
purposes, Python's complex hash function presumably has been designed so there's
a good chance they are.  (But before doing this, I'd peek at the hashing
function inside complexobject.c if I were you: looks kindda suspicious to me
<wink>.)

For example:

   hash_cmp = lambda a,b: cmp(hash(a), hash(b))
   cpx_list = [3+0j, 1+1j, 1+2j, 2+1j, 2+2j, 1+0j, 0+3j]
   cpx_list.sort(hash_cmp)
   print cpx_list

yields:

   [(1+0j), (3+0j), (1+1j), (2+1j), (1+2j), (2+2j), 3j]

Even better, you could create a custom complex "cmp" function that works in a
comparison-of-a-pair-of-real-values sense, which you could then feed to Python's
sort method.  For fun, I decided to try to come up with a lambda for that:

   Cartesian_cmp = lambda a,b: (a.real != b.real) * cmp(a.real, b.real) + \
                               (a.real == b.real) * cmp(a.imag, b.imag)

(The essential trick here is to use a multiply by an equality to avoid the "if"
statement lambda doesn't allow.)

With that comparison function in hand, the following:

   cpx_list.sort(Cartesian_cmp)

yields:

   [3j, (1+0j), (1+1j), (1+2j), (2+1j), (2+2j), (3+0j)]

which is the same as the manual result I gave at top.

And then there's the polar (magnitude/phase) version:

   from math import *
   polar_cmp = lambda a,b: (abs(a) != abs(b)) * cmp(abs(a), abs(b)) + \
(abs(a) == abs(b)) * cmp(atan2(a.imag, a.real), atan2(b.imag, b.real))

which yeids:

   [(1+0j), (1+1j), (2+1j), (1+2j), (2+2j), (3+0j), 3j]

never-let-theory-stand-in-the-way-of-practice-ly y'rs,

=g2

_____________________________________________________________________

Grant R. Griffin                                       g2 at dspguru.com
Publisher of dspGuru                           http://www.dspguru.com
Iowegian International Corporation            http://www.iowegian.com