Skip to main content
7 of 8
added 21 characters in body
rhermans
  • 37.7k
  • 4
  • 64
  • 156

SequenceSplit, Longest, Plus

My approach is to take advantage of the built-in SequenceSplit and ask for the Longest pattern with the Condition(/;) that it adds up (Plus) to less than 20 (<20).

SequenceSplit[alist, {Longest[a__]} /; Plus[a] < 20 :> {a}] 

Analysis

This solution is reasonably short and idiomatic and doesn't create any lingering definitions. Good enough for short lists, but as it's based on pattern matching will not perform well for huge lists. See performance analysis below. The evaluation is not element by element, but on the whole sub-list (Plus[a] < 20).

What is most interesting about your question is that all the available tools like Split and SplitBy make element by element comparisons, and we have no (AFAIK) efficient built-in functions that split based on a test that is over the whole sublist. I hope to see other answers that do direct sequential tests over sublists which may scale well over long lists.

I am looking forward to seeing various other answers. Nice question!

Performance

This is rather slow for long lists, compare with the best alternatives

  • 268494 split by @BenIzd (fast, short and simple)
  • 268537 accumLess5 by @AlexeyPopkovor (impressive best performance, moderate length, complicated)

Measuring with AbsoluteTiming at various lengths.

ListPlot[ Table[ {l, First@AbsoluteTiming[ SequenceSplit[ RandomInteger[{1, 10}, l] , {Longest[a__]} /; Plus[a] < 20 :> {a} ]; ] } , {l, 10, 1200, 50} ] , PlotTheme -> "Scientific" , FrameLabel -> {"List length", "Time [s]"} ] 

enter image description here

This is in a rather old i7-4770 CPU @ 3.40GHz @BenIzd shows both a better performing algorithm and a newer computer.

rhermans
  • 37.7k
  • 4
  • 64
  • 156