[Tutor] Re: sorting into lists

[Thorsten Kampe]

* Tim Wilson
> l = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4]
>
> I'm trying to figure out a good way to turn this list into
> [[1, 1, 1], [2, 2], [3, 3, 3, 3], [4, 4]]

Mathematically spoken you want a "quotient set" that is the original
list partitioned into "equivalence classes". In your case the function
defining "equivalence" is the identity 'f(x) = x'

#v+
def quotient_set(seq, func):
    """ partition seq into equivalence classes """
    quotient_set = {}
    for item in seq:
        quotient_set.setdefault(repr(func(item)),[]).append(item)
    return quotient_set
#v-

"quotient_set" keeps the class representatives ("keys") for further
processing, so you have to get rid of them:
quotient_set(l, lambda x: x).values()

Equivalence classes are *very* useful. Two examples:

You want to write a dictionary of words where all words starting with
the same character should be in a separate chapter. 'func' is
'word[0]'.

You want to group numbers into bins where each 0 < x < 10 goes in
bin1, 10 <= x < 100 goes in bin2, 100 <= x < 1000 goes in bin3, etc.
'func' is modf(log10(x))[1]


Thorsten