11
$\begingroup$

For example, here is a list

{{1, "u"}, {6, "d"}, {3, "u"}, {4, "d"}, {2, "u"}, {5, "u"}, {3, 
  "d"}, {1, "d"}, {4, "u"}, {2, "d"}, {5, "d"}, {6, "u"}}

The default canonical order for integer is 1,2,3,4

The default canonical order for letters is a,b,c,d,

But now I want to sort this list according to canonical integer order while "u" should be ordered before "d", how to achieve this easily?

The example list I gave here has a good structure, so can be solved with specific tricks. But the problem is general. How to sort list of mixed types of elements with each type a specified canonical order?

Improve this question
$\endgroup$
10
  • $\begingroup$ I'd define a function which assigns appropriate "weights" to elements then use SortBy or KeySortBy after casting the List as an Association (which I expect is faster, but haven't verified empirically). $\endgroup$
    – IPoiler
    Nov 2, 2015 at 2:39
  • $\begingroup$ SortBy[list, {First, Switch[#[[2]], "u", -1, "d", 1] &}] for your particular example works. $\endgroup$
    – J. M.'s lack of A.I. ♦
    Nov 2, 2015 at 2:57
  • $\begingroup$ Will your real world usage always only be "u" and "d" or will it be other letters of the alphabet? $\endgroup$
    – Mike Honeychurch
    Nov 2, 2015 at 5:07
  • $\begingroup$ Are you by any chance building a Wick Contraction generator? $\endgroup$
    – evanb
    Nov 3, 2015 at 0:53
  • $\begingroup$ @MikeHoneychurch other letter is possible, and even strings, they serve as labels $\endgroup$
    – matheorem
    Nov 3, 2015 at 0:57

5 Answers 5

Reset to default
14
$\begingroup$ 
SortBy[l, {First@#, -ToCharacterCode@Last@#} &]
(*{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4, 
  "u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}*)

Or the same, but slightly shorter code

SortBy[l, {#, -ToCharacterCode@#2} &@@#&]

Edit

The following uses the same sorting strategy but is much faster (by using this):

fns = {1000 # &, ToCharacterCode@# &};
l[[Ordering[Subtract @@@ Transpose@MapThread[Map, {fns, Transpose[l]}]]]]
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ using ToCharacterCode! upvote $\endgroup$
    – matheorem
    Nov 2, 2015 at 4:48
7
$\begingroup$

A simple approach giving the requested result is

SortBy[list, (#[[2]] /. {"u" -> 0, "d" -> 1}) + 100 #[[1]] &]    
(* {{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4, "u"}, 
    {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}} *)

In fact, even simpler is

SortBy[list, (# /. {"u" -> 0, "d" -> 1}) &]

Simpler yet is

SortBy[list, (# /. "u" -> 0) &]

Revised AbsoluteTiming with two new solutions

With so many solutions, it may be of interest to know their respective AbsoluteTimings, based on

list = Riffle[Map[{#, "u"} &, RandomSample[Range[100000]]], 
              Map[{#, "d"} &, RandomSample[Range[100000]]]];

Mike Honeychurch 0.397657

J.M. (comment) 0.468703

bbgodfrey (third solution) 0.589428

belisarius is forth (first solution) 0.811408

Jack LaVigne 11.2244

Modifications of solutions by J.M. and Mike Honeychurch, respectively, are even faster.

SortBy[list, {First, Switch[#, "u", -1, "d", 1] &}]  (* 0.385315 *)

Flatten[Reverse[Partition[Sort[list], 2], 2], 1]  (* 0.25386 *)
Improve this answer
$\endgroup$
3
  • $\begingroup$ I like this this one, clever! But why "d" -> 1/10, "d" -> 1 is OK. A mistake? $\endgroup$
    – matheorem
    Nov 2, 2015 at 4:23
  • $\begingroup$ @matheorem You are correct. "d" assigned any number bigger than that assigned to "u" works. I carried forward the logic of my first solution without thinking. Thanks for the correction. I have simplified my solution accordingly. $\endgroup$
    – bbgodfrey
    Nov 2, 2015 at 5:05
  • $\begingroup$ For large lists Sort can often be slow. Using Ordering could possibly speed up my solution for your large test sample. $\endgroup$
    – Mike Honeychurch
    Nov 2, 2015 at 23:37
4
$\begingroup$

Your limited example implies that you want to reverse the canonical order for the letters in position 2 so that "u" will appear before "d". I've assumed that all letters of the alphabet could appear in position 2 so if that is the case then this would do it:

Flatten[Reverse[GatherBy[Sort[list], First], 2], 1]

...but there is probably a more straight forward method, perhaps using SortBy.

Edit

As mentioned in comments with @bbgodfrey it is often more efficient to use Ordering for large lists rather than Sort. Also @bbgodfrey notes that Partition could be used instead of GatherBy.

Flatten[Reverse[Partition[list[[Ordering[list]]], 2], 2], 1]
Improve this answer
$\endgroup$
5
  • $\begingroup$ Straightforward or not, your solution is remarkably fast, especially when GatherBy is replaced by Partition. $\endgroup$
    – bbgodfrey
    Nov 2, 2015 at 14:14
  • $\begingroup$ I just noticed a typo in my earlier comment, which is why I deleted it. Ordering[list] should have been enclosed in double-brackets, not single ones. I corrected my error in your answer. Unfortunately, with the correction list[[Ordering[list]]] offers no advantage over Sort[list], although Partition still does. Sorry. $\endgroup$
    – bbgodfrey
    Nov 3, 2015 at 0:14
  • $\begingroup$ @bbgodfrey yes you're right. Maybe Sort has been rewritten in recent versions. Certainly in older version Ordering used to smash Sort. $\endgroup$
    – Mike Honeychurch
    Nov 3, 2015 at 0:34
  • $\begingroup$ On the other hand, list[[Flatten[Reverse[Partition[Ordering[list], 2], 2]]]] offers a noticeable speed advantage, probably because Reverse is acting on indices rather than on list elements. Of course, your original solution with GatherBy offers a flexibility that most other solutions lack. $\endgroup$
    – bbgodfrey
    Nov 3, 2015 at 1:02
  • 1
    $\begingroup$ @bbgodfrey I think there is enough information now to satisfy the OP $\endgroup$
    – Mike Honeychurch
    Nov 3, 2015 at 1:08
2
$\begingroup$

I think a general solution is to perform the first test followed by the second test in case of ties.

Sort[list, first[test] || tie[first] && second[test]]

For your specific example

list = {{1, "u"}, {6, "d"}, {3, "u"}, {4, "d"}, {2, "u"}, {5, "u"}, 
        {3, "d"}, {1, "d"}, {4, "u"}, {2, "d"}, {5, "d"}, {6, "u"}}

With the integers sorted on the first element and then "u" preceding "d" for the second element this translates to:

Sort[list, #1[[1]] < #2[[1]] ||
    (#1[[1]] == #2[[1]] && OrderedQ[{#2[[2]], #1[[2]]}]) &]

which gives

{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"},
  {4, "u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}
Improve this answer
$\endgroup$
1
  • $\begingroup$ I believe bbgodfrey's answer is better. I see that in the documentation for SortBy it states. SortBy[list, {f1, f2}...} breaks ties by successively using the values obtained from the fi. $\endgroup$
    – Jack LaVigne
    Nov 2, 2015 at 3:55
0
$\begingroup$

To actually answer the question (not the specific example), you could create a recursive function. It would take a list of comparison functions, compare the first elements using the first function, and only use the rest if the first elements are the same.

ClearAll[compare];
compare[a_, b_, test_] /; Length@a == 1 := test[[1]][a[[1]], b[[1]]];
compare[a_, b_, test_] := test[[1]][a[[1]], b[[1]]] ||
   a[[1]] == b[[1]] && compare[Rest@a, Rest@b, Rest@test];

In action:

Sort[list, compare[##, {Less, Greater}] &]

{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4, "u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}

And it works with elements of any length, with any sort of comparison, e.g.

r = RandomInteger[{0, 10}, {1000, 3}];
Sort[r, compare[##, {Less, Greater, Abs[5 - #1] < Abs[5 - #2] &}] &]
Improve this answer
$\endgroup$

Your Answer

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

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