Function Repository Resource:

PartitionWhile

Source Notebook

Partition a list by a condition on the sublists

Contributed by: Daniele Gregori

ResourceFunction["PartitionWhile"][list,crit]

partitions a list into sublists satisfying a condition.

Details and Options

PartitionWhile splits a collection into sublists comprised of consecutive elements which satisfy a given condition.

The function crit must take a list as input and return True or False.

ResourceFunction["PartitionWhile"][{i₁,i₂,…},crit] splits the data after i_k, if crit[{…,i_k}] is True but crit[{…,i_k,i_k+1}] is False.

The first argument of PartitionWhile can be a List to be partitioned. The second argument is a function which determines the condition which the partitions must satisfy.

The resulting sublists are such that the function evaluates to True on each of them.

In detail, the algorithm implements a double loop for each element of the list and its successive elements. The first subpartition is built by starting to add the list elements after the function first evaluates to True until the function evaluates to False on some successive element. Then the second subpartition is searched in the same way, starting from this last element and the program continues until the end of the list.

No offset parameter is currently implemented and the partitions can be made only at the first Level of the list argument.

By comparison, the core function Partition splits a list into subparts of or UpTo a certain Length.

PartitionWhile accepts the following option:

"ShortestPartitions"

True

change the length of the partitions

Different partitions, always satisfying the given condition, can be determined through different values for this option:

True

split always at the Shortest partition

False

search always the Longest partition

search k-1 next elements after the shortest partition

Examples

Basic Examples (2)

Partition a list of integers by imposing a condition on their Total:

In[1]:=

Out[1]=

In[2]:=

Out[2]=

Partition a list of random strings by a condition on their ByteCount:

In[3]:=

Out[3]=

In[4]:=

Out[4]=

In[5]:=

Out[5]=

Scope (4)

Partition a list of numbers by any logical condition:

In[6]:=

Out[6]=

Verify the totals:

In[7]:=

Out[7]=

Partition a list of natural numbers so each partition adds up to a prime number:

In[8]:=

Out[8]=

The totals are all prime:

In[9]:=

Out[9]=

Create partitions containing two prime values each:

In[10]:=

Out[10]=

Partition a text by a condition on some Characters in it:

In[11]:=

Out[11]=

Select substrings until there are three "a" characters in each:

In[12]:=

Out[12]=

In[13]:=

Out[13]=

Options (6)

ShortestPartitions (6)

By default, the splitting of the original list happens as soon as the Shortest possible partition is found:

In[14]:=

Out[14]=

In[15]:=

Out[15]=

It is also possible to search, for each element, the Longest possible partition until the end of the list:

In[16]:=

Out[16]=

However, with this option the partition algorithm becomes essentially quadratic and inefficient on a large scale:

In[17]:=

Out[17]=

In[18]:=

Out[18]=

In[19]:=

Out[19]=

A possible middle ground can sometimes be found by setting the option "ShortestPartitions" to an integer k >= 2, to search a longer partition k-1 elements after the shortest is found:

In[20]:=

Out[20]=

In[21]:=

Out[21]=

This effectively implements a (Monte Carlo) randomized algorithm, that is often correctly reproducing the longest partitions in an always efficient way:

In[22]:=

Out[22]=

In[23]:=

Out[23]=

In any case, the different k-next-to-shortest partitions can be of independent interest:

In[24]:=

Block[{max = 12, lenL, diff},
lenL = Flatten[Table[
Comap[{Map[Length, #] &}, ResourceFunction["PartitionWhile"][integers, Total[#] <= 10 &, "ShortestPartitions" -> n]], {n, 1, max}], 1];
(*Print[Grid@DeleteDuplicates@lenL];*)
diff = Table[If[
lenL[[i]] != lenL[[i + 1]], {i + 1, Diff[lenL[[i]], lenL[[i + 1]], "Combined"]}, Nothing], {i, 1, max - 1}];
Prepend[diff, Style[#, Bold] & /@ {"k-Shortest", "lengths Diff"}]] // Grid

Out[24]=

Applications (4)

The following list of data (scraped from arXiv) has very irregular element sizes:

In[25]:=

In[26]:=

Out[26]=

If you try to upload a too large Partition of it unto a Databin, you may exceed the size limits:

In[27]:=

Out[27]=

In[28]:=

Out[28]=

An optimal partition can be found instead through PartitionWhile[list,ByteCount[#]<=n&]:

In[29]:=

Out[29]=

In[30]:=

Out[30]=

The DatabinUpload is now successful:

In[31]:=

Out[31]=

Properties and Relations (5)

PartitionWhile[list,Length[#]<=n&] is equivalent Partition[list,UpTo[n]]:

In[32]:=

Out[32]=

In[33]:=

Out[33]=

In[34]:=

Out[34]=

In[35]:=

Out[35]=

PartitionWhile[list,Apply[SameQ,#]&] is equivalent Split[list]:

In[36]:=

In[37]:=

Out[37]=

In[38]:=

Out[38]=

In some cases (but see the comments in Possible Issues), PartitionWhile[list,Apply[SameQ,f[#]]&] is equivalent to SplitBy[list,f]:

In[39]:=

Out[39]=

In[40]:=

Out[40]=

In[41]:=

Out[41]=

In many cases, the output of PartitionWhile[list,fun] is equivalent to that of the built-in SequenceCases, but it implements a significantly faster algorithm:

In[42]:=

Out[42]=

In[43]:=

Out[43]=

In[44]:=

Out[44]=

In some cases, the output of PartitionWhile[list,fun] is different from SequenceCases, because of a different criterion for sequence splitting:

In[45]:=

Out[45]=

In[46]:=

$SequenceCases[{1, 2, 3, 4, 5, -20, 6, 12}, _?(Total[#] <= 10 &)] /. {} -> Nothing$

Out[46]=

The output of SequenceCases can be always recovered by setting the option "ShortestPartitions" to False:

In[47]:=

Out[47]=

Possible Issues (2)

Only partitions for conditions evaluating to True are returned:

In[48]:=

Out[48]=

So if the condition is always evaluated to False, you can use its contrary:

In[49]:=

Out[49]=

Compare with SplitBy:

In[50]:=

Out[50]=

Similarly, when the condition is evaluated sometimes to True and sometimes to False, only the former cases are returned:

In[51]:=

Out[51]=

The different behaviour of SplitBy can then be reproduced as follows:

In[52]:=

Out[52]=

In[53]:=

Out[53]=

Neat Examples (2)

Take the low level definition code and generate a much faster compiled version:

In[54]:=

$pwlTot[list_] := With[{fun = Total[#] <= 1000 &}, Block[{len, i, j, first, last, elq, prtind}, len = Length[list]; prtind = {}; For[i = 1, i <= len, i++, first = i; last = 0; For[j = i, j <= len, j++, elq = fun[list[[i ;; j]]]; If[elq, last = j, If[last != 0, Break[]]]]; If[last != 0, i = last; AppendTo[prtind, {first, last}]]]; Map[Take[list, #] &, prtind]]]$