5
$\begingroup$

As the title states - does a unique order exist for any Mathematica list to be sorted by the Sort[] function (or as returned by a function that treats lists as sets)?

While I'm pretty sure the answer is yes, the kinds of elements you can throw into a Mathematica list seems so general and varied (numbers, strings, symbols, images, graphs, other lists, etc., etc.) that I thought to make sure.

(The reason this question occurred to me is an exercise question asked in the book I just started learning Mathematica from: Write a function SubsetQ[list1, list2] that checks whether list1 is a subset of list2. My solution is

SubsetQ[lis1_, lis2_] := Intersection[lis1, lis2] == Union[lis1, {}]
(* thanks to Simon Woods' correction, and assuming Intersection and Union sort canonically *)

but that implicitly assumes that the two lists on either side of the equality check will be sorted in the same order.)

Improve this question
$\endgroup$
16
  • $\begingroup$ "Write a function SubsetQ[]..." - you've already seen MemberQ[]? $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Apr 3, 2013 at 8:17
  • $\begingroup$ Yes, I have. What solution would you like to suggest? (If it involves iteration, then that occurred to me, but since the book hasn't gotten to it yet I didn't consider it any further.) $\endgroup$
    – Aky
    Commented Apr 3, 2013 at 8:31
  • 3
    $\begingroup$ There is a canonical order. See : reference.wolfram.com/legacy/v5_2/book/section-A.3.9 $\endgroup$
    – andre314
    Commented Apr 3, 2013 at 8:39
  • 1
    $\begingroup$ @belisarius I would say since in Mathematica anything can be a list-element, Intersection must deal with general lists, which implies that its sorting function should be one that can sort any expression type. And since canonical sorting is such (and I don't think any other sorting is used generally in Mathematica) I would presume Intersection uses canonical sorting. To prove it would require someone to test all the specifications of the standard order linked by andre above. So in short: no, I don't know how to quickly test Intersection's sorting order :) $\endgroup$
    – István Zachar
    Commented Apr 3, 2013 at 9:16
  • 3
    $\begingroup$ From my experience, the answer is yes - the default sorting function is the same for Union, Intersection and Complement. As a side note, you could avoid this problem in this particular case by using something like SubsetQ[lis1_, lis2_] := Complement[list1, list2] === {}. $\endgroup$
    – Leonid Shifrin
    Commented Apr 3, 2013 at 10:12

1 Answer 1

Reset to default
2
$\begingroup$

As several others have pointed out, there exists a canonical ordering for any Mathematica expression. Quoting the list:

  • Integers, rational and approximate real numbers are ordered by their numerical values.
  • Complex numbers are ordered by their real parts, and in the event of a tie, by the absolute values of their imaginary parts.
  • Symbols are ordered according to their names, and in the event of a tie, by their contexts.
  • Expressions are usually ordered by comparing their parts in a depth-first manner. Shorter expressions come first.
  • Powers and products are treated specially, and are ordered to correspond to terms in a polynomial.
  • Strings are ordered as they would be in a dictionary, with the upper-case versions of letters coming after lower-case ones. Ordinary letters appear first, followed in order by script, Gothic, double-struck, Greek and Hebrew. Mathematical operators appear in order of decreasing precedence.

In your specific case, you can avoid having to sort anything by just taking the Complement, as Leonid mentioned:

SubsetQ[lis1_, lis2_] := Complement[list1, list2] === {}
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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