Raymond Hettinger <pyt...@rcn.com> writes:
> So, it looks like the relevant comparison values can be stored in
> nested lists:
>
> list_of_lists = \
> [[1, [3, [], []],
> [7, [5, [], []], []]],
> [19, [23, [], []],
> []],
> ]
Now you've copied all the data out of the original tree, which is even
worse than putting a class wrapper around it. The comparison remains
(asymptotically) as expensive as before, too.
> Are there any of these trees that cannot be transformed
> (by a key function) into an equivalent nested list of lists
> and values so that the trees can be directly compared to one another
> using Python's normal built-in recursive comparison order for lists?
I think so. Say you want to change the numeric comparisons so that
even numbers always sort before odd numbers, ie.
-4 < -2 < 0 < 2 < 4 < ... < -999 < ... -1 < 1 < 3 ...
I don't think there is a way to re-encode the numbers so they
can be compared with direct integer comparison. Even if there is,
I think there are reasonable orderings on the trees themselves that
can't possibly be embedded in the standard python comparison order.
I might be able to construct an example using ordinal diagrams from
proof theory.
--
http://mail.python.org/mailman/listinfo/python-list
