Command to take the first elements of a list that match a pattern - Mathematica Stack Exchange most recent 30 from mathematica.stackexchange.com 2019-08-25T19:10:16Z https://mathematica.stackexchange.com/feeds/question/64455 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://mathematica.stackexchange.com/q/64455 4 Command to take the first elements of a list that match a pattern Sultan of Swing https://mathematica.stackexchange.com/users/19987 2014-10-30T02:15:02Z 2014-11-03T02:24:39Z <p>I want to find the number of elements in a list in a row that match a certain pattern.</p> <p>So for this list</p> <pre><code>{1,1,1,1,0,0,0,1,1,1} </code></pre> <p>It should return "4" because there are four 1's in a row and then other stuff. I don't care that there are more 1's later on. I just want to find the number of consecutive integers in a row, starting from the beginning of the list. Is there a simple way of doing this?</p> <p><strong>Edit: I just realized my question was very poorly worded. I wanted to find the number of elements in a row starting from the beginning, regardless of what that element is.</strong></p> https://mathematica.stackexchange.com/questions/64455/-/64456#64456 1 Answer by kglr for Command to take the first elements of a list that match a pattern kglr https://mathematica.stackexchange.com/users/125 2014-10-30T02:36:46Z 2014-10-30T10:00:14Z <p><strong>Update 2:</strong> Based on OP's latest clarification:</p> <pre><code>lfF = With[{x = First@#}, LengthWhile[#, # == x &amp;]] &amp; lfF@{1, 1, 1, 1, 0, 0, 0, 1, 1, 1} (* 4 *) lfF@{0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1} (* 2 *) </code></pre> <p>or</p> <pre><code>lfF2 = Length@First@Split@# &amp;; lfF2@{1, 1, 1, 1, 0, 0, 0, 1, 1, 1} (* 4 *) lfF2@{0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1} (* 2*) </code></pre> <hr> <p><strong>Update:</strong> Per comments on the original version, revised to account for lists that do not start with <code>1</code>:</p> <pre><code>list = {0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1}; Length@First@Select[Split[list], First@# == 1 &amp;, 1] (* 4 *) Length@First@Split[Flatten[Position[list, 1]], #2 - #1 &lt;= 1 &amp;] (* 4 *) First@Cases[list, {Except ... , x : Longest[1 ..], ___} :&gt; Length[{x}], {0}] (* 4 *) </code></pre> <hr> <p><strong>Original post:</strong></p> <pre><code>list = {1, 1, 1, 1, 0, 0, 0, 1, 1, 1}; Length@First@Split[list] (* 4 *) LengthWhile[list, # == 1 &amp;] (* 4 *) </code></pre> https://mathematica.stackexchange.com/questions/64455/-/64457#64457 2 Answer by Michael E2 for Command to take the first elements of a list that match a pattern Michael E2 https://mathematica.stackexchange.com/users/4999 2014-10-30T02:46:22Z 2014-11-02T14:27:26Z <p>For what it's worth, a much better pattern (time complexity of order <code>n</code> instead of <code>n^2</code>), but still with a similar problem that Mr. Wizard pointed out. It is perhaps interesting to wonder about the difference between these two patterns.</p> <pre><code>Replace[list, {x__, Except[First[list]], ___} :&gt; Length[{x}]] /. y_List :&gt; Length[y] </code></pre> <p>First version (time complexity of order <code>n^2</code>):</p> <pre><code>list = {1, 1, 1, 1, 0, 0, 0, 1, 1, 1}; Replace[list, {y : Longest@Repeated[x_], ___} :&gt; Length[{y}]] (* 4 *) </code></pre> <hr> <p>Mr. Wizard's comparison:</p> <pre><code>Needs["GeneralUtilities`"] f1[a_] := LengthWhile[a, MatchQ@First@a] f2[list_] := Replace[list, {y : Longest@Repeated[x_], ___} :&gt; Length[{y}]] f3[list_] := Replace[list, {x__, Except[First[list]], ___} :&gt; Length[{x}]] /. y_List :&gt; Length[y] g = (SeedRandom; Clip @ RandomInteger[100, #]) &amp;; (*first zero at position 78*) BenchmarkPlot[{f1, f2, f3}, g, 2^Range, "IncludeFits" -&gt; True, TimeConstraint -&gt; 30] </code></pre> <p><img src="https://i.stack.imgur.com/0tF4Q.png" alt="Mathematica graphics"></p> <p>It is interesting that <code>Longest</code> is super-fast when the list is shorter than <code>77</code> and consists of all ones. It's too bad that a final <code>BlankNullSequence[]</code> does not short-circuit the pattern-matching.</p> https://mathematica.stackexchange.com/questions/64455/-/64458#64458 3 Answer by Dr. belisarius for Command to take the first elements of a list that match a pattern Dr. belisarius https://mathematica.stackexchange.com/users/193 2014-10-30T02:51:45Z 2014-10-30T04:16:33Z <pre><code>l = {0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1} LengthWhile[l[[LengthWhile[l, # != 1 &amp;] + 1 ;;]], # == 1 &amp;] (* 4 *) </code></pre> <p>Edit:</p> <p>and this is dedicated to <em>that</em> special person:</p> <pre><code>k = LengthWhile; l[[l~k~(# != 1 &amp;) + 1 ;;]]~k~(# == 1 &amp;) (* 4 *) </code></pre> https://mathematica.stackexchange.com/questions/64455/-/64477#64477 1 Answer by Sultan of Swing for Command to take the first elements of a list that match a pattern Sultan of Swing https://mathematica.stackexchange.com/users/19987 2014-10-30T09:21:34Z 2014-10-30T09:21:34Z <p>I want to thank everybody for their answers! I wanted to post an answer I saw in another question here on MSE but I can't seem to find it right now, but this was the solution that worked the simplest:</p> <pre><code>Length[Split[LIST][]] </code></pre> <p>So Using <code>Split</code> partitions the list as I wanted, and then I can just take the first element of that partitioned list, and find the length of it. So here is a sample:</p> <pre><code>list = {1, 1, 1, 1, 1, 2, 4, 5, 5, 5, 5, 1, 1, 1, 1, 1} Length[Split[list][]] </code></pre> <p>gives</p> <pre><code>{1, 1, 1, 1, 1, 2, 4, 5, 5, 5, 5, 1, 1, 1, 1, 1} 5 </code></pre> <p>As desired. Again I didn't come up with this; I saw it somewhere else and I would like to link to it, but cannot find it.</p> https://mathematica.stackexchange.com/questions/64455/-/64479#64479 5 Answer by Mr.Wizard for Command to take the first elements of a list that match a pattern Mr.Wizard https://mathematica.stackexchange.com/users/121 2014-10-30T09:50:24Z 2014-10-31T21:21:14Z <p>Regarding the updated description of your problem while <code>Split</code> is very clean it is not optimal unless the overall list is relatively short. As an example consider this data:</p> <pre><code>SeedRandom; a = RandomChoice[{"a", "b", "c"}, 1*^7]; </code></pre> <p>It begins with:</p> <pre><code>{"c", "c", "b", "a", . . .} </code></pre> <p>The method from your answer takes significant time:</p> <pre><code>Needs["GeneralUtilities`"] (* v10 package *) Length[Split[a][]] // AccurateTiming </code></pre> <blockquote> <pre><code>1.303075 </code></pre> </blockquote> <p>A method that does not process the entire list can be <em>much</em> faster:</p> <pre><code>LengthWhile[a, MatchQ @ First @ a] // AccurateTiming (* v10 operator form *) </code></pre> <blockquote> <pre><code>0.0000185558 </code></pre> </blockquote> <p>For versions before 10 see kguler's <strong>Update 2</strong> code.</p> <hr> <h2>Sidebar: timings of a pattern-based approach</h2> <p>Michael made the claim that his method is faster than <code>LengthWhile</code>. In the particular test he used, where nearly the entire list consists of the same element it starts with, it is, but elsewhere it performs <em>extremely</em> poorly. For example:</p> <pre><code>Needs["GeneralUtilities`"] f1[a_] := LengthWhile[a, MatchQ @ First @ a] f2[list_] := Replace[list, {y : Longest@Repeated[x_], ___} :&gt; Length[{y}]] g = (SeedRandom; Clip @ RandomInteger[100, #]) &amp;; (* first zero at position 78 *) BenchmarkPlot[{f1, f2}, g, 2^Range, "IncludeFits" -&gt; True, TimeConstraint -&gt; 30] </code></pre> <p><img src="https://i.stack.imgur.com/1W5nI.png" alt="enter image description here"></p> <p>In this test the first differing element occurs at position 78 but the length of the list past that grows. We see that <code>LengthWhile</code> correctly handles this in constant time whereas <code>Replace</code> explodes which should not happen if the pattern engine were well optimized.</p> <p>Let us examine the pattern behavior by adding a <code>PatternTest</code> to <code>x_</code>:</p> <pre><code>SeedRandom list = Clip @ RandomInteger[100, 1000]; inc = (i++; True) &amp;; i = 0; Replace[list, {y : Longest@Repeated[x_?inc], ___} :&gt; Length[{y}]] i </code></pre> <blockquote> <pre><code>77 71148 </code></pre> </blockquote> <p>Observe that despite there being only 77 ones at the start of the list, and the list in its entirety being only 1000 elements long, <code>Replace</code> performs over 71 <em>thousand</em> element tests. This makes no sense but it is an old problem that I have <a href="https://stackoverflow.com/q/8522876">complained about before.</a></p> https://mathematica.stackexchange.com/questions/64455/-/64537#64537 1 Answer by SquareOne for Command to take the first elements of a list that match a pattern SquareOne https://mathematica.stackexchange.com/users/19960 2014-10-31T00:51:01Z 2014-11-03T02:24:39Z <p>... If your list </p> <pre><code>list={1,1,1,1,0,0,0,1,1,1}; </code></pre> <p>was a String :</p> <pre><code>mystring = (StringJoin @@ ToString /@ list) (* 1111000111 *) </code></pre> <p>you could also do :</p> <pre><code>StringCases[mystring, s : (StartOfString ~~ (x_) ..) :&gt; StringLength@s][] (* 4 *) </code></pre> <p>or</p> <pre><code>StringPosition[mystring, (StartOfString ~~ (x_) ..)][[1, -1]] (* 4 *) </code></pre> <p>It is also fast because it just searchs the "start of the string".</p> <p><strong>Edit: Benchmarking</strong> </p> <pre><code>Needs["GeneralUtilities`"]; f1s[st_] := StringCases[st, s : (StartOfString ~~ (x_) ..) :&gt; StringLength@s][]; f2s[st_] := StringPosition[st, (StartOfString ~~ (x_) ..)][[1, -1]]; gs = (SeedRandom; StringJoin @@ ToString /@ Clip@RandomInteger[100, #]) &amp;; </code></pre> <p>then</p> <pre><code>BenchmarkPlot[{f1s, f2s}, gs, 2^Range, "IncludeFits" -&gt; True, TimeConstraint -&gt; 30] </code></pre> <p>gives a log(n) behaviour</p> <p><img src="https://i.stack.imgur.com/gq86T.png" alt="enter image description here"></p> <p>whereas for longer lists ...</p> <pre><code>BenchmarkPlot[{f1s, f2s}, gs, 2^Range, "IncludeFits" -&gt; True, TimeConstraint -&gt; 30] </code></pre> <p><img src="https://i.stack.imgur.com/G8eru.png" alt="enter image description here"></p> <p>For relative time comparison here is what I get for the benchmarking of the other posts :</p> <p><img src="https://i.stack.imgur.com/JFKJm.png" alt="enter image description here"> </p> <p><strong>Update : for integers > 9</strong></p> <p>In the original post, I did not take into account (as remarked in the comment) that the list could contain integers >9 ... (however all the benchmarking and examples in the proposed answers do not treat this case).</p> <p>Anyway, let's take the proposed list in the comment :</p> <pre><code>list = {1, 1, 111, 1111, 11111, 2, 3}; </code></pre> <p>and transform it into a "useful" string</p> <pre><code>mystring = " " &lt;&gt; StringDrop[ToString@list, 1] (* 1, 1, 111, 1111, 11111, 2, 3}*) (*you could also test directly :*) (*mystring="1,1,111,1111,11111,2,3"*) </code></pre> <p>then</p> <pre><code>StringCases[mystring, a : (StartOfString ~~ Shortest[(x__) ~~ ","] ..) :&gt; StringLength@a/(StringLength@x + 1)][] (*2*) </code></pre> <p>does the job and should be fast because it focuses on the start of the string.</p> <p>Of course, the question was not about strings, but I thought it was interesting to extend and test ;) </p>