Partitioning with varying partition size

The core solution

If I understand your question I previously wrote a function for this purpose.
The core of that function is:

dynP[l_, p_] := 
 MapThread[l[[# ;; #2]] &, {{0} ~Join~ Most@# + 1, #} & @ Accumulate @ p]

Version 8 users have Internal`PartitionRagged which has the same syntax for the basic case.

dynP[Range@6, {1, 2, 3}]

{{1}, {2, 3}, {4, 5, 6}}

dynP[Range@8, {3, 1, 2, 1}]

{{1, 2, 3}, {4}, {5, 6}, {7}}

Extended version

Since this answer proved popular I decided to do a full rewrite of dynamicPartition:

  • Shorter code with less duplication
  • Better performance and lower argument testing overhead
  • Partitioning of expressions with heads other than List

dynamicPartition[list, runs] splits list into lengths runs.

dynamicPartition[list, runs, All] appends all remaining elements in a single partition.

dynamicPartition[list, runs, spec1, spec2, ...] passes specifications specn to Partition for the remaining elements.

dPcore[L_, p : {q___, _}] := Inner[L[[# ;; #2]] &, {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 && Length@L >= Tr@p

(This code no longer uses dynP shown above.)

Usage Examples:

dynamicPartition[Range@12, {4, 3}, All]

{{1, 2, 3, 4}, {5, 6, 7}, {8, 9, 10, 11, 12}}

dynamicPartition[Range@12, {4, 3}, 2]

{{1, 2, 3, 4}, {5, 6, 7}, {8, 9}, {10, 11}}

dynamicPartition[h[1, 2, 3, 4, 5, 6, 7], {3, 1}, 2, 1, 1, "x"]

h[h[1, 2, 3], h[4], h[5, 6], h[6, 7], h[7, "x"]]

Packed arrays

Please note that one special but practically important case is when the list you want to split is a packed array, or can be converted into one. Here is an illustration. First, we create a large (and apparently unpacked) test list:

(test = Flatten[Range/@Range[5000]])//Developer`PackedArrayQ

(*  False  *)

We now split it:

(res = dynP[test,Range[5000]]);//AbsoluteTiming

(* {0.2939453,Null} *)

We can see that the sublists are, or course, unpacked as well:

Developer`PackedArrayQ/@res//Short

(*  
      {False,False,False,False,False,False,False,False,
      <<4984>>,False,False,False,False,False,False,False,False}
*)

Converting to a packed array admittedly takes some time:

test1 = Developer`ToPackedArray[test]; // AbsoluteTiming

(* {0.1660157, Null} *)

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:

(res1 = dynP[test1,Range[5000]]);//AbsoluteTiming

(*  {0.0644531,Null}  *)

and all the sublists are now also packed:

Developer`PackedArrayQ/@res1//Short

(*
   {True,True,True,True,True,True,True,True,True,
    <<4982>>,True,True,True,True,True,True,True,True,True}
*)

which has a large impact on the total memory consumption as well:

ByteCount/@{res,res1}

(*    {400320040,50900040}    *)

The technique of converting sub-lists of a ragged lists to packed form was already discussed a few times here on SE, e.g. here. In this particular case, dynP 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.


Update: see section three for a significant optimization.

Reading your question again today I realize that I did not understand it completely the first time. Since my existing answer is already quite long I am posting an additional answer.

This method is not as fast as dynamicPartition but it finally does what you asked.

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 <= Length@L
  ]

Examples:

partitionBy[Range@10, # &]

{{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}}

partitionBy[Range@10, 2 &]

{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}

partitionBy[Range@12, Mod[#, 3, 1] &]

{{1}, {2, 3}, {4, 5, 6}, {7}, {8, 9}, {10, 11, 12}}

On long lists you may need to increase $IterationLimit.

While I enjoyed writing the functional code above it seems a procedural approach is faster:

partitionBy2[L_List, func_] :=
 Reap[Block[{i = 1, p = 0, x, n = Length@L},
   While[
     (x = p + func[i++]) <= n,
     Sow @ L[[p + 1 ;; (p = x)]];
   ]
 ]][[2, 1]]

Compiled function

For considerably greater speed with compilable length-functions the following may be used:

partitionBy3[L_List, func_] := 
 Inner[L[[# ;; #2]] &, ##, List] & @@ 
  Compile[{{n, _Integer}}, 
    Module[{i = 1},
     {#[[;; -3]] + 1, #[[2 ;; -2]]} & @
       NestWhileList[# + func[i++] &, 0, # <= n &]
    ]
  ] @ Length @ L

Example:

partitionBy2[Range@1*^7, Mod[#, 17, 1] &] // Timing // First

partitionBy3[Range@1*^7, Mod[#, 17, 1] &] // Timing // First

3.76

1.014


New in 11.2 is TakeList:

TakeList[Range[10], {2, 3, 5}]

{{1, 2}, {3, 4, 5}, {6, 7, 8, 9, 10}}

Tags:

List Manipulation

Partitions

Recent Posts