Talk:Order two numerical lists: Difference between revisions

Line 73:

::: Lexicographic comparison of two lists meaning comparing corresponding elements from either list, ''probably'' from left to right, and the ordering of the first unequal pair decides the ordering of the two lists. The elements need to be comparable and have good ordering. Say the lists are strings "ax" and "ay", the most natural ordering is "ax" < "ay". When comparing "ax" and "aY", depends on what comparison function you use for letters, it could be "ax" < "aY" if using case insensitive cmp, or "ax" > "aY" if comparing ASCII code case sensitively. Comparison function of strings is lexicographic, that of the letters is not: it can be whatever that has a good ordering. Replace "letters" with "numbers", "comparing letters" with "comparing numbers", and you lexicographically compare list of numerical values.

::: When two lists are of different lengths, "comparing corresponding elements" needs clarification when one list runs out. One way is, conceptually, you can pad the shorter list with some default value so they are equal length again. For strings, this default value may be considered as code point 0, so comparing "ab" to "abcde" can be considered as the same between "ab\0\0\0" and "abcde". It's convenient and practical most of the time, but if you were to pad strings with odd stuff like "W", you could still have well ordered comparisons, it's just not going to be terribly intuitive (imagine a diction where "abT" < "ab" = "abW" < "abX"). --[[User:Ledrug|Ledrug]] 05:48, 30 November 2011 (UTC)

==Is the task statement consistent?==

I learnt about the mathematical meaning of lexicographic sorting, rather than the lexicographic dictionary ordering through this task and the discussions here, thanks. This did make me look deeply at the task description, and I think there may exist an inconsistency in the language of the task description. It might have been put in whilst trying to cover the case of equal lists.

This statement:

:''The function should accept two lists as arguments and return <code>true</code> if the first list should be ordered before the second, and <code>false</code> otherwise.''

Uses the word should so if comparing two equal lists, empty or not, it seems this implies that the answer must be false, as an ordering is indeterminate.

This statement:

:''If the first list runs out of elements the result is true. false otherwise.''

When following the (rather opaque to me), mathematical description of the process, you would run out of elements if the process is:

<pre>:label1

Try to get next A element

If fail to get as there are no more A elements:

If there are more B elements:

# B is A with extra tacked on and so A precedes B

return True

Else:

return True # ???

Else:

# We have the next element of A

Try to get next B element

If fail to get as there are no more B elements:

# A is B with extra tacked on and so A does not precede B

return False

Else:

If this A element precedes this B element:

return True

Else:

If this B element precedes this A element:

return False

# Got equal elements from A and B

Goto :label1</pre>

If you were to focus on the ??? point in the pseudocode, it seems that the first quote from the task description says that the return value should be False, whilst the second says True.

* Could someone comment on my interpretation of the mathematical description from the wp article [[wp:Lexicographical order#Ordering of sequences of various lengths|link]].

* Other work beckons so I am unable to suggest a remedy at this time.

--[[User:Paddy3118|Paddy3118]] 07:26, 30 November 2011 (UTC)