Talk:Order two numerical lists: Difference between revisions

If the relations can be strictly defined, might as well:

:: Given two lists of numbers: <math>\{a_i\}</math> where <math>i = 1, 2, \cdots M</math> and <math>\{b_j\}</math> where <math>j = 1, 2, \cdots N</math>, the lexicographic ordering between <math>a</math> and <math>b</math> is said to be <math>a < b</math> iff:

::* there exists an index <math>x</math> where <math>a_x < b_x</math>, and <math>a_i = b_i</math> for all <math>i < x</math>; or

::* <math>M < N</math>, and <math>a_i = b_i</math> for all <math>1 \leq i \leq M</math>.

:: Note that by convention, when we say "condition such and such for all i in set A" and A turns out to be empty, this condition is considered sastified.

:: Also note that, the task seems to have sorting in mind; however, if elements can be equal to each other, you ''must'' have a <math>\leq</math> comparison instead of <math><</math>, so equality also needs to be defined. The reason: a list <math>a</math> is considered sorted if for any pairs of indices <math>i, j</math> where <math>1 \leq i \leq j \leq M</math>, the condition is met: <math>a_i \leq a_j</math>. The last term can't be stated as <math>a_i < a_j</math> if elements may compare equal, or list (1, 2, 2) will not have a sorted permutation. --[[User:Ledrug|Ledrug]] 09:26, 30 November 2011 (UTC)