Partitioning with varying partition size - Mathematica Stack Exchange most recent 30 from mathematica.stackexchange.com 2019-08-25T14:43:22Z https://mathematica.stackexchange.com/feeds/question/7511 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://mathematica.stackexchange.com/q/7511 69 Partitioning with varying partition size sjdh https://mathematica.stackexchange.com/users/515 2012-06-27T08:55:08Z 2018-11-07T11:56:45Z <p>How can I partition a list into partitions whose sizes vary? The length of the <span class="math-container">\$k\$</span>'th partition is a function <span class="math-container">\$f(k)\$</span>.</p> <p>For example: if <span class="math-container">\$l = \{1, 2, 3, 4, 5, 6\}\$</span> and <span class="math-container">\$f(k) = k\$</span>. Then the partitioning <span class="math-container">\$p\$</span> would look like <span class="math-container">\$p = \{\{1\},\{2, 3\},\{4,5,6\}\}\$</span></p> <hr> <p>In Mathematica 11.2, the builtin <a href="https://reference.wolfram.com/language/ref/TakeList.html" rel="nofollow noreferrer"><code>TakeList</code></a> will do this.</p> https://mathematica.stackexchange.com/questions/7511/-/7512#7512 57 Answer by Mr.Wizard for Partitioning with varying partition size Mr.Wizard https://mathematica.stackexchange.com/users/121 2012-06-27T09:19:27Z 2012-07-05T10:53:06Z <h2>The core solution</h2> <p>If I understand your question I <a href="https://stackoverflow.com/a/5433867/618728">previously wrote a function</a> for this purpose.<br> The core of that function is:</p> <pre><code>dynP[l_, p_] := MapThread[l[[# ;; #2]] &amp;, {{0} ~Join~ Most@# + 1, #} &amp; @ Accumulate @ p] </code></pre> <p><strong>Version 8 users have <code>Internal`PartitionRagged</code> which has the same syntax for the basic case.</strong></p> <pre><code>dynP[Range@6, {1, 2, 3}] </code></pre> <blockquote> <pre><code>{{1}, {2, 3}, {4, 5, 6}} </code></pre> </blockquote> <pre><code>dynP[Range@8, {3, 1, 2, 1}] </code></pre> <blockquote> <pre><code>{{1, 2, 3}, {4}, {5, 6}, {7}} </code></pre> </blockquote> <hr> <h2>Extended version</h2> <p><em>Since this answer proved popular I decided to do a full rewrite of <code>dynamicPartition</code>:</em></p> <ul> <li>Shorter code with less duplication</li> <li>Better performance and lower argument testing overhead</li> <li>Partitioning of expressions with heads other than <code>List</code></li> </ul> <blockquote> <p><code>dynamicPartition[<em>list</em>, <em>runs</em>]</code> splits <em>list</em> into lengths <em>runs</em>.</p> <p><code>dynamicPartition[<em>list</em>, <em>runs</em>, All]</code> appends all remaining elements in a single partition.</p> <p><code>dynamicPartition[<em>list</em>, <em>runs</em>, <em>spec<sub>1</sub></em>, <em>spec<sub>2</sub></em>, ...]</code> passes specifications <em>spec<sub>n</sub></em> to <code>Partition</code> for the remaining elements.</p> </blockquote> <pre><code>dPcore[L_, p : {q___, _}] := Inner[L[[# ;; #2]] &amp;, {0, q} + 1, p, Head@L] dPcore[L_, p_, All] := dPcore[L, p] ~Append~ Drop[L, Last@p] dPcore[L_, p_, n__] := dPcore[L, p] ~Join~ Partition[L ~Drop~ Last@p, n] dynamicPartition[L_, p : {__Integer}, x___] := dPcore[L, Accumulate@p, x] /; ! Negative@Min@p &amp;&amp; Length@L &gt;= Tr@p </code></pre> <p>(This code no longer uses <code>dynP</code> shown above.)</p> <p><strong>Usage Examples:</strong></p> <pre><code>dynamicPartition[Range@12, {4, 3}, All] </code></pre> <blockquote> <pre><code>{{1, 2, 3, 4}, {5, 6, 7}, {8, 9, 10, 11, 12}} </code></pre> </blockquote> <pre><code>dynamicPartition[Range@12, {4, 3}, 2] </code></pre> <blockquote> <pre><code>{{1, 2, 3, 4}, {5, 6, 7}, {8, 9}, {10, 11}} </code></pre> </blockquote> <pre><code>dynamicPartition[h[1, 2, 3, 4, 5, 6, 7], {3, 1}, 2, 1, 1, "x"] </code></pre> <blockquote> <pre><code>h[h[1, 2, 3], h, h[5, 6], h[6, 7], h[7, "x"]] </code></pre> </blockquote> <h2>Packed arrays</h2> <p>Please note that one special but practically important case is when the list you want to split is a <a href="https://mathematica.stackexchange.com/questions/3496/what-is-a-mathematica-packed-array/">packed array</a>, or can be converted into one. Here is an illustration. First, we create a large (and apparently unpacked) test list:</p> <pre><code>(test = Flatten[Range/@Range])//Developer`PackedArrayQ (* False *) </code></pre> <p>We now split it:</p> <pre><code>(res = dynP[test,Range]);//AbsoluteTiming (* {0.2939453,Null} *) </code></pre> <p>We can see that the sublists are, or course, unpacked as well:</p> <pre><code>Developer`PackedArrayQ/@res//Short (* {False,False,False,False,False,False,False,False, &lt;&lt;4984&gt;&gt;,False,False,False,False,False,False,False,False} *) </code></pre> <p>Converting to a packed array admittedly takes some time:</p> <pre><code>test1 = Developer`ToPackedArray[test]; // AbsoluteTiming (* {0.1660157, Null} *) </code></pre> <p>But if you do some manipulations with this list many times, this will pay off. Also, often you end up with a packed list from the start. Anyway, now splitting this list is several times faster:</p> <pre><code>(res1 = dynP[test1,Range]);//AbsoluteTiming (* {0.0644531,Null} *) </code></pre> <p>and all the sublists are now also packed:</p> <pre><code>Developer`PackedArrayQ/@res1//Short (* {True,True,True,True,True,True,True,True,True, &lt;&lt;4982&gt;&gt;,True,True,True,True,True,True,True,True,True} *) </code></pre> <p>which has a large impact on the total memory consumption as well:</p> <pre><code>ByteCount/@{res,res1} (* {400320040,50900040} *) </code></pre> <p>The technique of converting sub-lists of a ragged lists to packed form was already discussed a few times here on SE, e.g. <a href="https://mathematica.stackexchange.com/questions/1665/efficient-conditional-mean-on-a-large-data-set/1671#1671">here</a>. In this particular case, <code>dynP</code> will do that automatically when the initial list is packed, but it is still good to keep in mind, for example to avoid accidental unpacking of sublists during whatever further processing you want to perform on the resulting ragged list.</p> https://mathematica.stackexchange.com/questions/7511/-/7514#7514 9 Answer by István Zachar for Partitioning with varying partition size István Zachar https://mathematica.stackexchange.com/users/89 2012-06-27T09:45:56Z 2012-06-27T09:45:56Z <p>This is a bit different than Mr.Wizards excellent solution: it calculates the number of successively longer partitions (thus no irregular partitioning argument can be given) using the summation formula, and then does the same <code>Accumulate</code> &amp; extract inside a <code>MapThread</code>.</p> <pre><code>myPartition[list_] := Module[ {num = Ceiling[n /. First@Solve[{ n (1 + n)/2 == Length@list, n &gt; 0}]]}, MapThread[ Take[list, {#2, Min[Length@list, #2 + #1 - 1]}] &amp;, {Range@num, Most@FoldList[Plus, 1, Range@num]}] ]; myPartition@Range@20 </code></pre> <blockquote> <pre><code>{{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}} </code></pre> </blockquote> https://mathematica.stackexchange.com/questions/7511/-/7808#7808 40 Answer by Mr.Wizard for Partitioning with varying partition size Mr.Wizard https://mathematica.stackexchange.com/users/121 2012-07-02T15:01:33Z 2013-05-14T01:23:45Z <p><em>Update: see section three for a significant optimization.</em></p> <p>Reading your question again today I realize that I did <em>not</em> understand it completely the first time. Since my existing answer is already quite long I am posting an additional answer.</p> <p>This method is not as fast as <code>dynamicPartition</code> but it finally does what you asked.</p> <pre><code>partitionBy[L_List, func_] := Reap[partitionBy[L, func, 1, 0]][[2, 1]] partitionBy[L_List, func_, i_, pos_] := With[{x = pos + func[i]}, partitionBy[Sow @ L[[pos + 1 ;; x]]; L, func, i + 1, x] /; x &lt;= Length@L ] </code></pre> <p>Examples:</p> <pre><code>partitionBy[Range@10, # &amp;] </code></pre> <blockquote> <pre><code>{{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}} </code></pre> </blockquote> <pre><code>partitionBy[Range@10, 2 &amp;] </code></pre> <blockquote> <pre><code>{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}} </code></pre> </blockquote> <pre><code>partitionBy[Range@12, Mod[#, 3, 1] &amp;] </code></pre> <blockquote> <pre><code>{{1}, {2, 3}, {4, 5, 6}, {7}, {8, 9}, {10, 11, 12}} </code></pre> </blockquote> <p>On long lists you may need to increase <code>\$IterationLimit</code>.</p> <hr> <p>While I enjoyed writing the functional code above it seems a procedural approach is faster:</p> <pre><code>partitionBy2[L_List, func_] := Reap[Block[{i = 1, p = 0, x, n = Length@L}, While[ (x = p + func[i++]) &lt;= n, Sow @ L[[p + 1 ;; (p = x)]]; ] ]][[2, 1]] </code></pre> <hr> <h3>Compiled function</h3> <p>For considerably greater speed with compilable length-functions the following may be used:</p> <pre><code>partitionBy3[L_List, func_] := Inner[L[[# ;; #2]] &amp;, ##, List] &amp; @@ Compile[{{n, _Integer}}, Module[{i = 1}, {#[[;; -3]] + 1, #[[2 ;; -2]]} &amp; @ NestWhileList[# + func[i++] &amp;, 0, # &lt;= n &amp;] ] ] @ Length @ L </code></pre> <p>Example:</p> <pre><code>partitionBy2[Range@1*^7, Mod[#, 17, 1] &amp;] // Timing // First partitionBy3[Range@1*^7, Mod[#, 17, 1] &amp;] // Timing // First </code></pre> <blockquote> <p>3.76</p> <p>1.014</p> </blockquote> https://mathematica.stackexchange.com/questions/7511/-/25186#25186 10 Answer by Simon Woods for Partitioning with varying partition size Simon Woods https://mathematica.stackexchange.com/users/862 2013-05-14T13:03:15Z 2013-05-14T13:03:15Z <p>This won't win any prizes for performance, but perhaps if there was a prize for using the second argument of <code>Split</code> in ways that were never intended...</p> <pre><code>partitionBy[list_, func_] := Module[{f, i = func, k = 1}, _f := i-- &gt; 1 || (i = func[++k]); Split[list, f]] partitionBy[Range@12, Mod[#, 3, 1] &amp;] </code></pre> <blockquote> <pre><code>{{1}, {2, 3}, {4, 5, 6}, {7}, {8, 9}, {10, 11, 12}} </code></pre> </blockquote> https://mathematica.stackexchange.com/questions/7511/-/28403#28403 7 Answer by Kuba for Partitioning with varying partition size Kuba https://mathematica.stackexchange.com/users/5478 2013-07-11T08:09:11Z 2013-07-11T08:09:11Z <p>I have created today a question which was a duplicate of this (thanks to <a href="https://mathematica.stackexchange.com/users/5274/pinguin-dirk">Pinguin Dirk</a>).</p> <p>My attepmts are not very spophisticated but one may find them useful:</p> <p>Let <code>f[k]</code> be a list of lengths:</p> <pre><code>l = Range; p = {2, 3, 5}; </code></pre> <p><strong>1</strong></p> <pre><code>Take[l, {1, 0} + #] &amp; /@ (Partition[Prepend[Accumulate@p, 0], 2, 1]) </code></pre> <blockquote> <p>{{1, 2}, {3, 4, 5}, {6, 7, 8, 9, 10}}</p> </blockquote> <p><strong>2</strong></p> <pre><code>FoldList[{Take[#1[[ 2]], #2], Drop[#1[[ 2]], #2]} &amp;, {1, l}, p ][[ ;; , 1]] // Rest </code></pre> <blockquote> <p>{{1, 2}, {3, 4, 5}, {6, 7, 8, 9, 10}}</p> </blockquote> https://mathematica.stackexchange.com/questions/7511/-/123516#123516 14 Answer by masterxilo for Partitioning with varying partition size masterxilo https://mathematica.stackexchange.com/users/6804 2016-08-09T15:24:37Z 2016-08-14T14:34:31Z <p>This can be implemented elegantly with <a href="http://reference.wolfram.com/language/ref/FoldPairList.html" rel="noreferrer"><code>FoldPairList</code></a> and <a href="http://reference.wolfram.com/language/ref/TakeDrop.html" rel="noreferrer"><code>TakeDrop</code></a> (both new in v10.2), in fact it's one of the examples in the documentation:</p> <pre><code>FoldPairList[TakeDrop, Range, {2, 3, 5}] </code></pre> <blockquote> <pre><code>{{1, 2}, {3, 4, 5}, {6, 7, 8, 9, 10}} </code></pre> </blockquote> <pre><code>FoldPairList[TakeDrop, Range, Range] </code></pre> <blockquote> <pre><code>{{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}, {11, 12, 13, 14, 15}} </code></pre> </blockquote> https://mathematica.stackexchange.com/questions/7511/-/157095#157095 16 Answer by Carl Woll for Partitioning with varying partition size Carl Woll https://mathematica.stackexchange.com/users/45431 2017-10-04T01:05:28Z 2017-10-04T01:05:28Z <p>New in 11.2 is <a href="http://reference.wolfram.com/language/ref/TakeList" rel="noreferrer"><code>TakeList</code></a>:</p> <pre><code>TakeList[Range, {2, 3, 5}] </code></pre> <blockquote> <p>{{1, 2}, {3, 4, 5}, {6, 7, 8, 9, 10}}</p> </blockquote>