14
$\begingroup$

One task that I frequently find myself doing in Mathematica is splitting lists into lists of sublists, using specific elements to define the break-points. This is particularly useful with imported files which often have a structure like this:

section 1
a
b
c
section 2 
d
e 
f

Upon import, this turns into

{"section 1", "a", "b", "c", "section 2", "d", "e", "f"}

I'd like to split this into sublists at the strings that mark sections, like so:

{{"a", "b", "c"}, {"d", "e", "f"}}

Doing this with Mathematica's library functions is pretty awkward. First, you want a predicate that tells you where the delimiting elements are:

delimiterQ[s_String] := StringMatchQ[s, "section "~~__]
delimiterQ[_]        := False

In cases like this, rule replacement seems like an elegant solution:

In[1]:= delimitingRule = {before___, _?delimiterQ, 
          Longest[run : Except[_?delimiterQ] ...], 
          after___} :> {before, {run}, after};
        {"section 1", "a", "b", "c", "section 2", "d", "e", "f"} //. delimitingRule
Out[1]= {{"a", "b", "c"}, {"d", "e", "f"}}

However, the performance of this kind of solution is truly atrocious, as you might expect (I got bored of waiting with a test list of 1000 elements after a couple minutes). The alternative I usually use is:

In[2]:= splitAtDelimiters[l_List, test_] :=
         With[{delimIndices = Flatten@Position[l, _?test, {1}], 
          len = Length@l},
          With[{first = First@delimIndices, last = Last@delimIndices},
           Take[l, #] & /@ Join[
             If[1 < first, {{1, first - 1}}, {}],
             # + {1, -1} & /@ Partition[delimIndices, 2, 1],
             If[last < len, {{last + 1, len}}, {}]]]];
In[3]:= splitAtDelimiters[
         {"section 1", "a", "b", "c", "section 2", "d", "e", "f"}, 
         delimiterQ]
Out[3]= {{"a", "b", "c"}, {"d", "e", "f"}}

This works OK, but I always think there must be a better way to do things whenever I generate a list of indices into a list just to immediately extract them all again. That sort of round trip is a Mathematica "code smell", IMO, and in this particular case there's a lot of extra work done to deal with corner cases involving delimiters at the begining or end of the list.

Any other suggestions? I think that there must be a way to do it with Split, but after trying a few obvious things I'm not sure what it is.

EDIT to add: My approach using Position has an annoying bug in cases where you are interested in splitting a list of lists (which is common when processing, say, Excel imports). The corrected version requires use of the Heads -> False option for Position:

splitAtDelimiters[l_List, test_] :=
 With[{delimIndices = 
    Flatten@Position[l, _?test, {1}, Heads -> False], len = Length@l},
   With[{first = First@delimIndices, last = Last@delimIndices},
    Take[l, #] & /@ Join[
     If[1 < first, {{1, first - 1}}, {}],
     # + {1, -1} & /@ Partition[delimIndices, 2, 1],
     If[last < len, {{last + 1, len}}, {}]]]]

Bugs like this make me think my unease with this approach is justified.

EDIT the second: rcollyer suggested I move this from StackOverflow.

$\endgroup$

9 Answers 9

13
$\begingroup$

The first thing that comes to mind is:

list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

delimiterQ[s_String] := StringMatchQ[s, "section " ~~ __]
delimiterQ[_] := False

SplitBy[list, delimiterQ][[2 ;; ;; 2]]
{{"a", "b", "c"}, {"d", "e", "f"}}

Szabolcs raised the concern that if the first element of list is not a delimiter this breaks. If you know in advance that the first element is not a delimiter you can use [[;; ;; 2]] -- if it is uncertain you might use this rather ugly blob of code:

#[[If[delimiterQ@#[[1, 1]], 2, 1] ;; All ;; 2]] & @ SplitBy[list, delimiterQ]

If you can create a list of all separators another option would be using Import. With your data in splitdat.txt:

Rest@Import["splitdat.txt", "Table", 
  "LineSeparators" -> {"section 1", "section 2"}, 
  "FieldSeparators" -> "\n"]
{{"a", "b", "c"}, {"d", "e", "f"}}

Likewise ReadList, which is probably faster:

ReadList["splitdat.txt",
  Word,
  WordSeparators -> "\n",
  RecordLists -> True,
  RecordSeparators -> {"section 1", "section 2"}
]
$\endgroup$
10
  • $\begingroup$ This is perfect, and it leaves the option of keeping the delimiters should I need them (which I sometimes do). $\endgroup$
    – Pillsy
    Feb 22, 2012 at 16:49
  • $\begingroup$ @Pillsy okay, great! But you should wait to Accept an answer until you have seen what everyone else has to offer. :-) $\endgroup$
    – Mr.Wizard
    Feb 22, 2012 at 16:51
  • $\begingroup$ This Split approach won't work if the list does not start with a delimiter. $\endgroup$
    – Szabolcs
    Feb 22, 2012 at 17:02
  • $\begingroup$ @Szabolcs if the list doesn't start with a delimiter just use [[;; ;; 2]] instead. It is not hard to test if the list starts with a delimiter. $\endgroup$
    – Mr.Wizard
    Feb 22, 2012 at 17:04
  • $\begingroup$ I think the SplitBy solution is superior as you may not know the number of "LineSeparators" or RecordSeparators present. It somewhat irks me that you can't pass something a little more dynamic to those like a StringExpression (e.g. "section " ~~ __) or a RegularExpression to allow for more variation in importing. $\endgroup$
    – rcollyer
    Feb 22, 2012 at 17:10
8
$\begingroup$

If you import your sample file as text, then do a StringSplit you have more control:

test="section 1\na\nb\nc\nsection 2\nd\ne\nf"
Rest/@StringSplit@StringSplit[test, "section "]

This outputs {{"a", "b", "c"}, {"d", "e", "f"}}

Edit In a comment, rcollyer complained about the inability to use RegularExpression. Using this approach you can:

StringSplit@StringSplit[test, "section " ~~ RegularExpression["\\d"]]

which has the same output as above.

$\endgroup$
1
  • $\begingroup$ An excellent alternative. $\endgroup$
    – Mr.Wizard
    Feb 22, 2012 at 16:55
7
$\begingroup$

Here is a solution based on a combination of rules and recursion, but not very efficient (the inefficiency spotted by @Pillsy, see below for the explanation):

Clear[splitAtDelimeters];
splitAtDelimeters[l_List, test_] :=
  Module[{split, h},
    h[{}] := h[];
    h[h[x___], h[y___]] := h[x, y];
    split[ls_] :=
      First@ReplaceList[
         ls,
         {{x___, el_?test, y___} :> h[h[{x}], split[{y}]], x_List :> h[x]},
         1];
    List @@ split[l]];

For example:

list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

delimiterQ[s_String] := StringMatchQ[s, "section " ~~ __]
delimiterQ[_] := False

splitAtDelimeters[list,delimiterQ]

(*
  ==> {{a,b,c},{d,e,f}}
*)

EDIT

As rightly noted by @Pillsy, the above solution is still quadratic complexity in the size of the list. I missed this point initially, but this is clearly due to massive list/ sequence copying in patterns like

{x___, el_?test, y___} :> h[h[{x}], split[{y}]]

(y is the culprit here).

Here is a linear time solution, based entirely on linked lists:

Clear[splitAtDelimetersLL];
splitAtDelimetersLL[l_List, test_] :=
  Module[{split, ll, llist, hh},
    SetAttributes[{ll, hh}, HoldAllComplete];
    llist = Fold[ll[#2, #1] &, ll[], Reverse@l];
    split[acc_, ll[_?test, t_], r_] := split[hh[], t, ll[r, acc]];
    split[acc_, ll[h_, t_], r_] := split[hh[acc, h], t, r];
    split[acc_, ll[], r_] := ll[r, acc];
    Map[
      Flatten[#, Infinity, hh] /. {hh[] :> Sequence[], hh[x__] :> {x}} &,
      List @@ Flatten[split[hh[], llist, hh[]], Infinity, ll]
    ]
  ];

It may be somewhat less elegant, but it avoids excessive copying characteristic for the previous one. It also is tail-recursive, so it affects $IterationLimit rather than $RecursionLimit, which is good. This solution is just as efficient as the one based on SplitBy, proposed by @Mr.Wizard, at least for this predicate / problem.

$\endgroup$
6
  • $\begingroup$ Leonid, I realize I hold you to a higher standard, but what is the benefit of this over SplitBy? Or are you showing how one can implement such a function himself? $\endgroup$
    – Mr.Wizard
    Feb 22, 2012 at 16:54
  • $\begingroup$ @Mr.Wizard I just think this is an interesting code pattern, based entirely on rules (and recursion) and still being efficient. I can imagine other cases when this can be useful and no simple function like Split or SplitBy will exist. For this particular case, I don't claim any superiority of my code. Also, the OP wished to have some rule-based solution for this, that was part of my motivation. So, yes, if you wish, this illustrates how to efficiently implement a version of SplitBy with only the replacement rules. $\endgroup$ Feb 22, 2012 at 17:00
  • $\begingroup$ Good enough for me. +1 $\endgroup$
    – Mr.Wizard
    Feb 22, 2012 at 17:05
  • 1
    $\begingroup$ @Leonid This is more efficient than my rule-based solution, but it's still O(n^2). Using rule-replacement with sequence-based patterns in lists is really hard to do efficiently. $\endgroup$
    – Pillsy
    Feb 22, 2012 at 17:21
  • $\begingroup$ @Pillsy Actually, you are right, I was not careful enough. Please see my edit for a linear-time solution. $\endgroup$ Feb 22, 2012 at 17:52
6
$\begingroup$

Inspired by rcollyer's state machine answer, I realized that with a little change you can generate index pairs to pass to Take, as in my original solution. The advantage of doing things this way is that, with a little help from Boole, you can easily recast the state machine as something that works in Compile.

compiledIndexer =
 Compile[{{tests, _Integer, 1}},
  With[{n = Length@tests},
   Module[{
     j = 1,
     fill = 0,
     result = ConstantArray[0, {2*Count[tests, 0], 2}],
     state = tests[[1]]},
     Do[
      If[BitXor[tests[[i]], state] == 1,
       result[[++fill]] = {j, i - 1};
       state = tests[[i]];
       j = i],
     {i, 2, n}];
    result[[++fill]] = {j, n};
    Take[result, fill]]]];

The rest of the function is just a one-liner. Well, a two-liner, because Compile can't return a zero-length list, so you need to specially handle an empty list:

splitWithCompile[{}, _] = {};
splitWithCompile[list_List, test_] :=
 With[{tests = Boole[test /@ list]},
  Take[list, #] & /@ compiledIndexer[tests]]

On my machine, this goes about 50% slower than Heike's SplitBy solution, but that's using Mathematica's bytecode compiler. I don't have a C compiler on this machine, so I can't really take full advantage of the Mathematica 8 compiler.

$\endgroup$
3
  • 1
    $\begingroup$ Pretty cool, +1. I'd recommend to replace ConstantArray (which is not compilable), with Table. $\endgroup$ Feb 22, 2012 at 19:08
  • $\begingroup$ @LeonidShifrin I tried that, and it didn't make a discernible difference in performance. It's just one external call, and there's no reason ConstantArray can't really fly here. $\endgroup$
    – Pillsy
    Feb 23, 2012 at 0:26
  • $\begingroup$ Agree - when it is not in a loop, there isn't much of a difference. I just like it when everything inside Compile is compiled, and usually bring pieces which can not be compiled outside of Compile, but this is a matter of personal preference :) $\endgroup$ Feb 23, 2012 at 0:29
5
$\begingroup$

This is a variation of Mr.Wizard's answer:

list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

delimiterQ[s_String] := StringMatchQ[s, "section " ~~ __]
delimiterQ[_] := False

Rest /@ Split[list, (Not[delimiterQ[#2]] &)]

Here, I'm specifying a test function to Split to decide where the list should be split. For a test function test, say, the list will be split between consecutive elements e1 and e2 if test[e1, e2] returns False. The next sublist will then start with e2. In this case the list will be split between e1 and e2 if Not[delimiterQ[e2]] == False, i.e. when delimiterQ[e2] == True.

$\endgroup$
3
  • $\begingroup$ To my surprise this appears to be faster than SplitBy. +1 ! $\endgroup$
    – Mr.Wizard
    Feb 22, 2012 at 17:03
  • $\begingroup$ This won't work correctly if the list doesn't start with a delimiter . $\endgroup$
    – Szabolcs
    Feb 22, 2012 at 17:10
  • $\begingroup$ @Szabolcs I guess you could do something like Split[list, (Not[delimiterQ[#2]] &)] /. a_String /; delimiterQ[a] :> Sequence[] instead $\endgroup$
    – Heike
    Feb 22, 2012 at 17:11
3
$\begingroup$

I know, late to the party, but after my answer for the Brainf*** parser, I have been thinking in terms of state machines. In this case, each instance of the pattern "section " ~~ __ signals a change in state from one section to the next, so it seems like a solution based upon Sow and Reap should be doable with a cached section delimiter, as follows

splitAtDelimeters[l_List, test_, out_:Rule]:=
Module[{del = ""},
 Reap[If[
      test@#,
      del = #,
      Sow[#, del]
      ] & /@ l, _, out][[2]]
 ]

 splitAtDelimeters[list, StringMatchQ[#, "section " ~~ __] &]
 (*
 {"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
 *)

Incidentally, this works "out of the box" for lists without a starting delimiter:

 splitAtDelimeters[Rest@list, StringMatchQ[#, "section " ~~ __] &]
 (*
 {"" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
 *)

Edit: As pointed out, the above code does not work for non-unique delimiters. An alternative is to track them separately, and recombine them at the end, as follows:

Clear[splitAtDelimeters2]
splitAtDelimeters2[l_List, test_, out_: Rule] :=
 Module[{del = {}, section = 1},
  Reap[If[test@#,
        del = {del, #}; section++,
        Sow[#, section]
        ] & /@ l, _, #2 &
     ][[2]] // MapThread[out, 
     With[{lstdels = Flatten[del], terms = #1},
      {If[Length@lstdels != Length@terms, {""}, {}]~Join~lstdels, 
       terms}]
     ] &
  ]

longList = Flatten@ConstantArray[list, {3}];
splitAtDelimeters[longList, StringMatchQ[#, "section " ~~ __] &]
(*
{"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}, 
 "section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}, 
 "section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
*)

Or, without a leading delimiter

splitAtDelimeters[Rest@longList, StringMatchQ[#, "section " ~~ __] &]
(*
{"" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}, 
 "section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}, 
 "section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
*)

This works by tagging each entry with a unique section number (section), and then using MapThread with the accumulated delimiters (del). The If is in there to ensure that the list of delimiters has the same length as the number of terms which will occur if the leading section is missing a delimiter.

$\endgroup$
6
  • $\begingroup$ This won't work when some delimeters are repeated several times, like e.g. in Flatten@ ConstantArray[list, {3}]. $\endgroup$ Feb 22, 2012 at 18:01
  • $\begingroup$ @LeonidShifrin you're right, I had assumed (incorrectly) that the delimiters would be unique. $\endgroup$
    – rcollyer
    Feb 22, 2012 at 18:06
  • $\begingroup$ @LeonidShifrin I added something that will work for non-unique delimiters. $\endgroup$
    – rcollyer
    Feb 22, 2012 at 18:25
  • $\begingroup$ @rcollyer Another trick for making the state machine work is to detect edges; this has the advantage that you can just use the value of test as your state. $\endgroup$
    – Pillsy
    Feb 22, 2012 at 18:37
  • $\begingroup$ @Pillsy that's what I did with the BF parser. Here, I thought I could do something a little simpler. $\endgroup$
    – rcollyer
    Feb 22, 2012 at 18:43
2
$\begingroup$
list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"}

In a sense it is good to retain section information, but it can be removed from the following alternatives, if required. The Sequence* functions are slow, so these must unfortunately be avoided for larger lists.

SequenceReplace[list, {s_String?(StringContainsQ["section"]), 
   h___String?(StringFreeQ["section"])} :> {s, h}]

{{"section 1", "a", "b", "c"}, {"section 2", "d", "e", "f"}}

Using :> {h} as the replacement pattern will generate sublists without the section delimiters.


The Split and SplitBy answers have appeared on this page previously along with the delimiter debate. I am using the StringFreeQ function as a predicate for demo.

Split[list, StringFreeQ[#2, "section"] &]

{{"section 1", "a", "b", "c"}, {"section 2", "d", "e", "f"}}


SplitBy[list, StringFreeQ[#1, "section"] &]

{{"section 1"}, {"a", "b", "c"}, {"section 2"}, {"d", "e", "f"}}

which can be partitioned in twos if required.


SequenceSplit[list, {x_String /; StringMatchQ[x, "section*"]}]

{{"a", "b", "c"}, {"d", "e", "f"}}

$\endgroup$
2
$\begingroup$
list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

A slot-free combination of Syed's answers:

SplitBy[list, StringFreeQ @ "section"][[2 ;; ;; 2]]

{{"a", "b", "c"}, {"d", "e", "f"}}

$\endgroup$
2
$\begingroup$

Using SplitBy and Select:

list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

Select[SplitBy[list, StringContainsQ[#, "section"] &], AllTrue[#, LetterQ] &]

(*{{"a", "b", "c"}, {"d", "e", "f"}}*)
$\endgroup$
1
  • 1
    $\begingroup$ +1, very nice, you can write this slot-free as Select[AllTrue@LetterQ]@SplitBy[list, StringContainsQ@"section"] $\endgroup$
    – eldo
    Dec 11, 2023 at 18:37

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.