2
$\begingroup$

I've defined ordering function:

myOrderingFunction[arg1_, arg2_]

which always return True or False.

Now I want to sort my list using this function, but unexpectedly:

In[28]:= OrderedQ[Sort[myList, myOrderingFunction], myOrderingFunction]

Out[28]= False

How is this even possible? When I apply Sort second time, myList become sorted properly. Of course, the issue may be hidden in my ordering function (how?), but first of all I want to exclude all kind of problems with Sort

EDIT Thanks for the replies, problem is definitely in ordering function, but I'am still confused. Situation is like this :

In[48]:= testList = {{Subscript[b, 1], Subscript[a, 2]}, Subscript[a, 
 3], {Subscript[b, 2], Subscript[a, 1]}};
{OrderedQ[#], OrderedQ[#, myOrderingFunction]} & /@ Subsets[unsorted, {2}]

Out[49]= {{False, False}, {True, True}, {True, True}}

In[50]:= Sort[testList]

Out[50]= {{Subscript[b, 1], Subscript[a, 2]}, {Subscript[b, 2], 
  Subscript[a, 1]}, Subscript[a, 3]}

In[51]:= Sort[testList, myOrderingFunction]

Out[51]= {Subscript[a, 3], {Subscript[b, 2], Subscript[a, 
  1]}, {Subscript[b, 1], Subscript[a, 2]}}

As you can see, usual OrderedQ and myOrderingFunctionreturns same results on every pair on the testList, but sorted lists are different (and both are not what I want, but that is another problem). To clarify, I just want to order some basic commutators in free group on $a_i, \ b_j$ in a natural way.

Also

In[55]:= OrderedQ[Sort[testList]]

Out[55]= True

In[56]:= OrderedQ[Sort[testList, myOrderingFunction], myOrderingFunction]

Out[56]= False

And (to reply to @JasonB answer)

In[57]:= OrderedQ[Sort[{{Subscript[b, 2], Subscript[a, 1]}, {Subscript[b, 1], 
    Subscript[a, 2]}}, myOrderingFunction], myOrderingFunction]

Out[57]= False

In[58]:= OrderedQ[Sort[{{Subscript[b, 1], Subscript[a, 2]}, {Subscript[b, 2], 
    Subscript[a, 1]}}, myOrderingFunction], myOrderingFunction]

Out[58]= False
$\endgroup$
  • 6
    $\begingroup$ I guess you need to show your function so folks can reproduce the problem. $\endgroup$ – george2079 Jan 25 '16 at 15:09
  • $\begingroup$ myOrderingFunction is kind of complicated (and I'm ashamed of my code also). Point is that it is definitely return True or False for all pairs of elements in myList. Just curious, maybe Sort have some issues that are known $\endgroup$ – user37190 Jan 25 '16 at 15:16
  • 1
    $\begingroup$ There is no room for shame on stackexchange :-) But seriously though, can you make this happen with a simpler sorting function? $\endgroup$ – Jason B. Jan 25 '16 at 15:27
  • 1
    $\begingroup$ @JasonB demonstrated a case where the ordering function may fail to ever sort the list in such a way, that it returns True for all pairs. Sort also does not check every element against every other element, it kind of assumes, that if a>b and b>c then a>c. If that doesn't hold for your ordering function, it may require more than a single pass to get everything ordered... or may get stuck in a situation it cannot escape, like {c, b, a}, but according to it c>a. $\endgroup$ – LLlAMnYP Jan 25 '16 at 17:03
9
$\begingroup$

You say

I've defined ordering function...which always return True or False.

But I don't think that's enough for it to be an ordering function. Consider this example, which also doesn't give the results you expect,

myOrderingFunction[arg1_, arg2_] := EvenQ[Round[Sin[ arg1 arg2]]];
list = RandomReal[20, 100];
OrderedQ[Sort[list, myOrderingFunction], myOrderingFunction]
(* False *)

It's easy to see that this isn't an ordering function, since it doesn't actually compare the elements,

myOrderingFunction @@ (Reverse@list[[3 ;; 4]])
myOrderingFunction @@ (list[[3 ;; 4]])
(* True *)
(* True *)

So maybe a quick change should make this work,

myOrderingFunction[arg1_, arg2_] := 
 Round[Sin[ arg1 ]] > Round[Sin[arg2]]
OrderedQ[Sort[list, myOrderingFunction], myOrderingFunction]
(* False *)

That's odd, it does compare now but still doesn't work. I think this is because this simple sorting function still fails one vital test,

OrderedQ[{1.2, 1.2}, myOrderingFunction]
(* False *)

So the comparison needs to have an $\leq$ instead of $<$,

myOrderingFunction[arg1_, arg2_] := 
 Round[Sin[ arg1 ]] >= Round[Sin[arg2]]
OrderedQ[{1.2, 1.2}, myOrderingFunction]
OrderedQ[Sort[list, myOrderingFunction], myOrderingFunction]
(* True *)
(* True *)
$\endgroup$
  • $\begingroup$ I think you hit the nail on the head, but with too complicated an example. Simply using myOrderingFunction[a_, b_] := a < b shows the same thing. Properly an ordering function must return True for the equality case. $\endgroup$ – george2079 Jan 25 '16 at 19:21
  • $\begingroup$ True, I was just trying to guess what OP might be up to. I was trying to look up what properties an ordering function should have, but found nothing authoritative. Besides the one you mention, I was thinking that if it returned False for {a,b}, then it must return true for the reverse. Are there any more requirements? $\endgroup$ – Jason B. Jan 25 '16 at 20:05
  • $\begingroup$ Thank you for the reply, I've included example of the list in the original post. All elements there are different, moreover two different ordering function which have same values on elements of the list leads to different sortings. $\endgroup$ – user37190 Jan 25 '16 at 21:56
  • $\begingroup$ @JasonB, myOrderingFunction returns False in both cases {a,b} and {b,a}, which is very strange, because it should not have any weird behavior, I will put code in original post. $\endgroup$ – user37190 Jan 25 '16 at 22:04
  • $\begingroup$ @user37190 - we literally can't go any farther unless you post the code for myOrderingFunction $\endgroup$ – Jason B. Jan 26 '16 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.