I don’t think the purpose of this thread is to validate whether [{1}, {2}, {3}] is a valid ordering, but to validate whether [{1}, {2}, {3}] is the only possible topological sort of the elements. Since [{1}, {2}, {3}] can be just as validly sorted as [{1}, {3}, {2}] and so on, it does not have a unique total order, and the function that Tim is looking for should return False.
A cubic-time example of the function should look roughly like this (implemented only case for 3+ elements):
def is_total_order(L):
size = len(L)
for i in range(size):
for j in range(i + 1, size):
for k in range(j + 1, size):
x, y, z = L[i], L[j], L[k]
if not (x <= y <= z and x <= z):
return False
return True
L = [{1},{3},{2}]
L.sort()
print(f'{L,is_total_order(L)=}') # L,is_total_order(L)=([{1}, {3}, {2}], False)
L.reverse()
L.sort()
print(f'{L,is_total_order(L)=}') # L,is_total_order(L)=([{2}, {3}, {1}], False)
Treat it like floating point wobblies. If they get a sort issue then read article on sort, comparisons, and total ordering as they will probably need more knowledge to understand the issue - provided by the article, and if the article becomes famous then those that know could point those that don’t at it if they determine that the article covers their case.
Python 2 said that int(2) <= list() <= long(1) was true because int(2) <= list() was true (because "int" <= "list" is true) and list() <= long(1) was true (because "list" <= "long" is true).
However, int(2) <= long(1) was false, so the check int(2) <= list() <= long(1) and int(2) <= long(1) would’ve returned false.
rather than slowing the sorting in any significant way here, maybe we could have a way to mark a type’s __lt__ as not suitable for stable sorting, then the sort only needs to observe this on a type to warn (this probably shouldn’t raise)
I don’t fully understand why this needs to be cubic.
I’d gather we need to compare all pairs in the sequence, so quadratic. If you imagine them in a matrix, all values in the lower triangle need to compare less than the diagonal, and the diagonal is less than all values in the upper triangle.
For y as diagonal, x in the lower triangle, and z in the upper triangle, this is implemented in below nested generator comprehension:
def is_total_order[T: annotated_types.SupportsLe](seq: Sequence[T], /) -> bool:
return all(all(x <= y for x in seq[: j]) # all `x` left of `y` must compare before `y`
and all(y <= z for z in seq[j + 1 :]) # `y` must compare before all `z` right of `y`
for j, y in enumerate(seq) # for all `y` in `seq`
)
(note the slicing makes for clear code, but would impact performance (unless seq is a sequence view); @blhsing’s index-based approach with i, j, k would perform better).
But perhaps I’m missing something and cubic is necessary. Please explain then.
Except “strict weak ordering” isn’t a concept Python intended to model. As mentioned before:
Sorting in particular takes not x < y and not y < x as implyingx == y. While that’s rarely important, it’s crucial in the logic for detecting “non-increasing runs”, to preserve stability when reversing such “in place”, to avoid disturbing the original order of stretches of equal elements.
The reason Python sticks to __lt__ isn’t to cater to strict weak orders, but to minimize the number of methods a user has to implement to participate in sorting (and use bisect and heapq functions). It always had total ordering in mind, and all its sort implementations before the current one freely invoked things like __eq__ too; (although only conceptually so, as those were written before “rich comparisons” were added, so all comparisons went through the older all-purpose __cmp__ dunder).
Yes! Users don’t give a rip about academic distinctions . Their complaints are always “I get a different permutation from sorting now than I used to get - sorting must be broken now!”., Verifying the transitivity of < is necessary but not sufficient to ensure that their comparison function defines a (unique) total order.
Users writing complicated comparison functions typically believe they are adequate to the task, so won’t mark their __lt__ implementations as unsafe. Or , as in the issue report I linked to, don’t bother to implement any of the rich comparison dunders, but rely instead on functools.cmp_to_key to magically supply what’s needed from a 3-outcome, all-purpose cmp funcrtion.
Because any way of verifying would be (much!) slower than sorting, I had in mind that verification would only be attempted if explicitly asked for, on a case-by-case basis. Given that opt-in possibility, the first response to “sorting is broken now1” issues could be “what happens if you pass (say) verify_unique=True?”)
Verifying transitivity indeed doesn’t require cubic time, and @mdickinson sketched a quadratic-time approach in one of the first replies here, and went on to post an implementation.
Besides a verifying function, if there is going to be a note in the docs, the red flag that a developer should be aware of and that could be IMO described briefly and without using terms like “total/partial ordering” and “topological sort” is this one: When a comparison function has a result “don’t know” instead of a clear answer “yes/no” or smaller/equal/greater". I’m not 100% sure if I remember it correctly, but any attempt to include a “tie-breaker” instead of “don’t know” must fail. (please correct me if this is not accurate).
To phrase that more precisely and succinctly, Python’s sort , for a well-defined result, requires that comparisons satisfy trichotomy (exactly one of <, ==, and > must obtain). Where ==means Python’s __eq__, not a more abstract equivalence relation.
I may have missed something, but for a single instance, surely falling back on object ids might allow for repeatable sorts even when objects compare equal?
Obviously if you have ObjectA() and ObjectB() that compare equal on your machine they might have different IDs to on mine and thus order differently, but at least repeated sorting would be deterministic rather than potentially reshuffling?
Of course this would not persist through garbage collection and recreation, so might still be unsatisfactory.
Leaving aside that Python’s sort doesn’t require that objects implement __eq__ at all (only __lt__), the primary point is to verify that the user’s comparison function is adequate so that the same permutation will always be returned, not just within a single run, but across multiple runs, across machines, across Python releases, and across Python implementations.
While covered later, while Python sticks to __lt__ for sorting, the intent was never to cater to (merely) partial orders of any flavor (it was to reduce the number of dunder methods users had to write). Sorting assumes trichotomy, and it’s really transitivity of <= that matters to it. So replace the above with:
for each pair i < j of indices, check that not a[j] < a[i]
Then the code would be simpler too, as there would be no need to treat equality/“equivalence” differently.
However, it appears it would also need to add checks that == on its own is an equivalence relation (sorry, no time now to make that coherent - more that == on its own is transitive too).
Trichotomy and reflexivity are different kinds of checks.
Half of that is still pointless, you don’t need z there. Instead of checking y<=z for two elements y and z, you can just wait until the second element becomes y and the first becomes x.
Both of you just check whether every element is less than or equal to every later element, and I don’t think that was the intention.
If Python had stuck to __le__ for sorting, it could’ve checked for equality with x <= y and y <= x. The check for < would’ve been x <= y and not y <= x.
Sad to say there’s another kind of insecurity in even the best of what’s been suggested so far. Given x < y, we cannot assume not y < x. That’s one of the things that a sane comparison would guarantee, but sanity is what we’re checking for. Believe me, user-supplied comparison functions came broken in ways that surprised everyone for years. Granted that most of those gross failures aren’t “theoretically interesting”, but they still need to be checked.
Sure! But it didn’t . It could have stuck to only one of any of <, >, <=, and >=.
I had no compelling reason for picking <, and it’s equally clumsy to stick to any of them.
A relatively weak reason was that <= are >= aren’t “primitive”, in the sense of trichotomy (or in IEEE-754’s later sense of that the outcome of a compare has one of four values (less, equal, greater, unordered)). And of all of them, < is most often used in texts and papers about ordering relations, although <= is pretty common too. > and >= are rarely used.
Here’s a first quick stab at verification via ensuring there is only one topological sort. To some extent, this doesn’t require verifying formal comparison properties at all, or trying to sort first. But that breaks down some (see comments) when faced with equal elements, and it would certainly be more useful for users to see messages about which formal properties their function doesn’t satisfy.
Sample output;
>>> check_total(list(range(1000)))
True
>>> check_total(list(range(1000)) * 2) # note that unsorted input is fine
True
>>> check_total([{2}, {1, 2, 4}])
True
>>> check_total([{2, 5}, {1, 2, 4}])
False
And it’s remarkably slow! Not sure why yet.
EDIT: id() isn’t really needed here, or the id2obji dict, but I’ll leave the code as-is. Instead we can simply feed elements’ indices into the topsorter. Quicker, smaller, shorter, and clearer. Note that we can’t feed the elements directly into the topsorter, because inputs to that need to be hashable, and list elements are arbitrary objects..
topsort code
from graphlib import TopologicalSorter, CycleError
def check_total(a):
ts = TopologicalSorter()
# Map id to object and its index.
# The index is to support useful error messages, but
# those aren't implemented yet.
id2obji = {}
for i, x in enumerate(a):
idx = id(x)
ts.add(idx)
id2obji[idx] = x, i
for y in a:
if x < y:
ts.add(id(y), idx)
try:
ts.prepare()
except CycleError:
# not a linear order
return False
# Accumulate the uniquely determined sorted prefix so far.
# Also for possible use in useful error messages.
inorder = []
while ts:
togo = ts.get_ready()
if len(togo) > 1:
# Next element isn't unique. That's OK if and only if
# they're all the same (equal).
for idx in togo:
x, i = id2obji[idx]
for idy in togo:
y, j = id2obji[idy]
# XXX This test doesn't stick to using `<`.
# Change that. But new code has to be added
# first, to verify that `not x < y and not y < x`
# implies `x == y`).
if not (x == y and y == x):
# Complain. The elements in inorder are uniquely
# ordered now, but the next elements aren't all
# equal. This _could_ be because it's only a
# partial order, or because the comparison function
# is just plain insane.
return False
inorder.extend(togo)
ts.done(*togo)
return True
. Their complaints are always “I get a different permutation from sorting now than I used to get - sorting must be broken now!”., Verifying the transitivity of