# Schwartzian Transform in Python?

Christian Tismer tismer at tismer.com
Thu Apr 27 12:18:30 EDT 2000

```Art Haas wrote:
...
> The python documentation doesn't make
> clear to me how to do things like "sort a list of lists by the second
> field in each sublist", which is what the Schwartzian transform is
> based on.

I think to remember an FAQ entry.
Here an (older) version of mine.
Not that today I would code that without
"transpose"
(left as an exercise to the reader)

You would use the below by supplying a metric like

sort(list, lambda x:x)

--------------------------

# this is taken from the FAQ and modified slightly:
"""
4.51. I want to do a complicated sort: can you do a Schwartzian
Transform in Python?

Yes, and in Python you only have to write it once:

def st(List, Metric):
def pairing(element, M = Metric):
return (M(element), element)
paired = map(pairing, List)
paired.sort()
return map(stripit, paired)

def stripit(pair):
return pair
"""

# now, this is my version:

def sort(List, Metric=None, stable=1) :
"""sort a list by a given metric function. The sort defaults
to be stable, keeping the order of elements which cannot be
distinguished by the metric"""

# transpose has problems with small lists, but in that
# case we don't need it:
if len(List) < 2: return List[:]

shaker = [List]
where = 0
if Metric :
# sorter is a list of function results
shaker.insert(0, map(Metric, List))
where = -1 # we are at the end
if stable :
# always stabilize behind the key
shaker.insert(1, range(len(List)))
# and we are still either at front or end
shaker = transpose(shaker)
shaker.sort()
return list(transpose(shaker)[where])

def transpose(x) :
"""transpose a sequence of lists into a list of tuples. This
is very fast, but doesn't work for len(x)==1"""
return apply(map, (None,)+tuple(x))

# Special problem with fast transpose:
# Due to map, transpose of a list with a single element
# returns a list, shape is lost.

# Solution:

def transpose(x) :
if len(x) == 1 :
return map(lambda y : (y,), x)
return apply(map, (None,)+tuple(x))

# General problems with transpose (not solvable here):
# A list of empty tuples returns an empty list (shape lost)

--------------------------

ciao - chris

--
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaunstr. 26                  :    *Starship* http://starship.python.net
14163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF