28
$\begingroup$

Is there an easy way to sort strings according to their natural ordering?
For example a list of file names

names = FileNames["~/Hex_*.dat"]
{"~/Hex_12.dat", "~/Hex_192.dat", "~/Hex_24.dat", "~/Hex_48.dat", "~/Hex_6.dat", "~/Hex_96.dat"}

I could use

SortBy[names, ToExpression[StringCases[#, RegularExpression[".*Hex_([0-9]+)\\.dat"] -> "$1"][[1]]] &]
{"~/Hex_6.dat", "~/Hex_12.dat", "~/Hex_24.dat", "~/Hex_48.dat", "~/Hex_96.dat", "~/Hex_192.dat"}

to get the file names into natural ordering, but this is neither elegant nor portable.
Any better suggestions?

Edit:
Many thanks for the answers.

But there is one problem left. Although all suggestions work with the above example, what can I do if there is more than one number in the path?
Files like:

A_1_1.dat, A_1_2.dat, ..., A_1_20.dat,
A_2_1.dat, A_2_2.dat, ..., A_2_20.dat,
...

Another problem I have encountered are rational numbers like:

T_0.23_run_1.dat, T_0.23_run_2.dat, ..., T_0.23_run_20.dat,
T_0.24_run_1.dat, T_0.24_run_2.dat, ..., T_0.24_run_20.dat,
...

$\endgroup$
2
  • $\begingroup$ Regarding your edit, my answer presciently addresses your first case. Actually, it addresses the second case to some degree as well. $\endgroup$
    – Mr.Wizard
    Sep 14, 2012 at 15:34
  • $\begingroup$ @Mr.Wizard Sorry, I was just editing while you answered, so I did not see your answer in time. $\endgroup$
    – Maxwell
    Sep 14, 2012 at 15:45

4 Answers 4

18
$\begingroup$

I share Leonid's reservations about basing the sort on simple string length. I would use a similar Ordering method, but I would parse things differently. Consider this test set:

names = {"~/Hex_12.dat", "~/Hex_192.dat", "~/Oct_99.dat", 
         "~/Hex_014.dat", "~/Hex_24_17.dat", "~/Hex_24_5.dat", 
         "~/Hex_48.dat", "~/Hex_6.dat", "~/Hex_96.dat", "~/Hex_nonum.dat"};

I would like my sort to recognize _24_17 as number 24 with a sub-number of 17. I would also like it to recognize 014 as 14. To that end I propose this method:

names[[Ordering @
  PadRight @ StringSplit[names, x : DigitCharacter .. :> FromDigits@x]
]]

(*
~/Hex_6.dat
~/Hex_12.dat
~/Hex_014.dat
~/Hex_24_5.dat
~/Hex_24_17.dat
~/Hex_48.dat
~/Hex_96.dat
~/Hex_192.dat
~/Hex_nonum.dat
~/Oct_99.dat
*)

Your edited question includes two additional examples. The first I anticipated in my answer above. The second, handling numbers with a decimal point, requires different parsing:

names2 = {"T_5_run_1.dat", "T_5_run_2.dat", "T_5_run_1.5.dat", 
          "T_0.23_run_1.dat", "T_0.23_run_2.dat", "T_0.23_run_20.dat", 
          "T_0.24_run_1.dat", "T_0.24_run_2.dat", "T_0.24_run_20.dat"};

names2[[Ordering @
  PadRight @ StringSplit[names2, x : NumberString :> ToExpression@x]
]]

(*
T_0.23_run_1.dat
T_0.23_run_2.dat
T_0.23_run_20.dat
T_0.24_run_1.dat
T_0.24_run_2.dat
T_0.24_run_20.dat
T_5_run_1.dat
T_5_run_1.5.dat
T_5_run_2.dat
*)
$\endgroup$
6
  • $\begingroup$ +1 Brilliant. PS: any reason for the latex outputs? $\endgroup$
    – Ajasja
    Sep 14, 2012 at 15:46
  • $\begingroup$ @Ajasja Thanks. Sorry, I realize I undid your edit with mine. No particular reason, other than wanting a format that made comparing lines easy and this was expedient. I presume you do not like it? $\endgroup$
    – Mr.Wizard
    Sep 14, 2012 at 15:48
  • $\begingroup$ Nope, I find it harder to read (on chrome win7). Is this tex font monospaced? I would argue for (* => *) or > . Screenshot $\endgroup$
    – Ajasja
    Sep 14, 2012 at 15:52
  • $\begingroup$ I agree with Ajasja on the latex issue. I think made this point to belisarius earlier too, and my issue was only the fact that on slightly choppy connections, mathjax does take time to load and it is worse still when using mobile devices. So I'd probably use it only where necessary. In this case, tabular format using monospaced text would've worked just as fine. If you don't mind, I can edit it but generally I try not to touch these as people sometimes are sensitive about their preferred way of formatting $\endgroup$
    – rm -rf
    Sep 14, 2012 at 16:31
  • $\begingroup$ @R.M yes, people (read: I) can be, but please go ahead in this case. $\endgroup$
    – Mr.Wizard
    Sep 14, 2012 at 16:37
22
$\begingroup$

This is short:

Last /@ Sort[{Characters@#, #} & /@ names]

{"~/Hex_6.dat", "~/Hex_12.dat", "~/Hex_24.dat", "~/Hex_48.dat", "~/Hex_96.dat", "~/Hex_192.dat"}

Alternatively:

Last /@ Sort[{ToExpression[StringJoin[Select[Characters@#, DigitQ]]], #} & /@ names]
$\endgroup$
4
  • 1
    $\begingroup$ +1 this is really nice, although I'm not clear on why this works. Why does Sort yield the correct result when used upon a list of characters? My though was that MMA treating a string like a character list was the reason for the unnatural sorting in the first place. $\endgroup$
    – Maxwell
    Sep 14, 2012 at 11:40
  • 6
    $\begingroup$ @Maxwell The reason it works is somewhat subtle : the lists with smaller numbers just happen to be shorter, so that Mathematica canonical ordering is fully suitable for this case, since smaller lists are moved to the left, and for equal-size lists, lexicographical ordering is used. So this code elegantly uses this peculiarity. $\endgroup$ Sep 14, 2012 at 11:56
  • 5
    $\begingroup$ A more concise and faster version of your method would be names[[Ordering[Characters[names]]]] $\endgroup$ Sep 14, 2012 at 14:04
  • $\begingroup$ As @R.M pointed out: The first solution fails if some files are named ~/Hex_012.dat. (So if some have leading zeroes and some do not.) $\endgroup$
    – Ajasja
    Sep 14, 2012 at 15:08
9
$\begingroup$

You anyway need to parse your list of file names in some way. Here is how I would do it:

Clear[sortByIndex];
sortByIndex[names : {__String}, pattern_] :=
    With[{inds = StringCases[names, pattern]},
        names[[Ordering[inds]]] /; FreeQ[inds, {}]
    ];
sortByIndex[__] := $Failed;

Since I extract indices all at once with StringCases, this should be considerably faster than if parsing would be a part of the comparison function in SortBy. I also included some error-checking.

It combines flexibility and error-checking, and encapsulates the sorting part, allowing the user to provide the parsing pattern. So, if we have the other lists as:

names1 = {"A_1_1.dat", "A_1_2.dat", "A_1_20.dat", "A_2_1.dat", "A_2_2.dat",  
          "A_2_20.dat"} 

and

names2 = {"T_0.23_run_1.dat", "T_0.23_run_2.dat", "T_0.23_run_20.dat",
   "T_0.24_run_1.dat", "T_0.24_run_2.dat", "T_0.24_run_20.dat"}

Then the sorting calls in all 3 cases can look like:

sortByIndex[
    names, 
    Shortest[___] ~~ n : DigitCharacter .. ~~ ___ :> ToExpression[n]
]

sortByIndex[
   RandomSample@names1, 
   Shortest[___] ~~ n : DigitCharacter .. ~~ "_" ~~ 
       m : DigitCharacter .. ~~ ___ :> Map[ToExpression, {n, m}]
]

and

sortByIndex[
    RandomSample@names2, 
    Shortest[___] ~~ n : NumberString ~~ "_run_" ~~ 
       m : DigitCharacter .. ~~ ___ :> Map[ToExpression, {n, m}]
]

Note how we can control how specific our patterns should be (I could have used __ in place of "_run_" in the latter case for example), to provide a tighter error-checking, if we need it.

$\endgroup$
7
$\begingroup$

A neat solution, in the same spirit as Chris' answer, would be to sort by the StringLength. This implicitly assumes that your file names do not have leading zeros (i.e. "Hex_00006.dat", for example). If this can be guaranteed, then smaller numbers will lead to shorter strings and the default tie breaking for strings of similar length is in the sense of OrderedQ, thus giving you the desired sorted list:

SortBy[names, StringLength]
(* {"~/Hex_6.dat", "~/Hex_12.dat", "~/Hex_24.dat", "~/Hex_48.dat", 
    "~/Hex_96.dat", "~/Hex_192.dat"} *)
$\endgroup$
6
  • 2
    $\begingroup$ While both Chris's and your solutions are concise, I feel a little uneasy with them because they use certain hidden assumptions valid only for a specific situation. This is a matter of taste, of course - in any case, I like both enough to upvote, +1. $\endgroup$ Sep 14, 2012 at 15:05
  • $\begingroup$ @LeonidShifrin Well, at least my assumptions are explicit and not hidden :) $\endgroup$
    – rm -rf
    Sep 14, 2012 at 15:26
  • 1
    $\begingroup$ My comment is not about the way you or Chris formulated your answer. In a way, it is a meta-comment and describes my personal views. If it reflects anything, it is probably my own shift from stressing the (and being mostly impressed with) very concise code to see that the code can service more cases than a given case at hand, or at least is structured so that it "self-describes" its own generality / applicability to similar problems and suggests a way to be extended. As I said, this is a matter of taste, and subjective as such, so you don't have to agree with me. $\endgroup$ Sep 14, 2012 at 15:57
  • $\begingroup$ I just noticed the edit in question, which only confirms (to me anyway) that my point was worth making. $\endgroup$ Sep 14, 2012 at 16:01
  • $\begingroup$ @LeonidShifrin Oh, not saying that your point wasn't relevant. I was rather thinking out aloud on the fact that I stated "This implicitly assumes..." in the answer, but then I go on to explain what I've assumed. That makes it explicit, so saying it was implicit in the first place was unnecessary. Yet, it's common in scientific writing... Don't bother, just some silly musings :) $\endgroup$
    – rm -rf
    Sep 14, 2012 at 16:36

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.