Grouping by total length of elements grouped

Question

How might one split a list of irregularly-long sublists into groups, each of which is shorter than a specified length?

For example, given the following input:

inlist = {{"a", "b", "c", "d", "e"}, {" "}, {"f", "g", "h"}, {"i", "j", "k", "l"}, {"m", "n", "o", "p"}};

and a maximum length of 10, an appropriate output would be

{{{"a", "b", "c", "d", "e"}, {" "}, {"f", "g", "h"}}, {{"i", "j", "k", "l"}, {"m", "n", "o", "p"}}};

as the total number of elements in each list is under 10. To be clear, the first list should be as close as possible to the target without going over, and then the second list should be as close as possible without going over, and so forth. Think of this as something like word-wrapping with characters of fixed width. Given a list longer than the target, it can be split in two.

Thus,

inlist2 = {{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"}, {"m", "n", "o", "p"}};

can be split in the middle of the first sublist, producing

{{{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}}, {{"k", "l"}, {"m", "n", "o", "p"}}}

Answer 1

Here is a way based upon GroupBy:

split[list_, n_] :=
  Module[{i=0}, MapIndexed[{Quotient[i++, n], {#2[[1]], #}}&, list, {2}]] //
  Flatten[#, 1]& //
  GroupBy[#, {First -> Last, First -> Last}]& //
  Values //
  Values

split[inlist, 10]
(* {{{"a", "b", "c", "d", "e"}, {" "}, {"f", "g", "h"}, {"i"}},
    {{"j", "k", "l"}, {"m", "n", "o", "p"}}} *)

split[inlist2, 10]
(* {{{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}},
    {{"k", "l"}, {"m", "n", "o", "p"}}} *)

Answer 2

A function to break up sublists longer than some integer n in a list lst is

limlen[lst_, n_] := FixedPoint[
    Flatten[Map[If[Length[#] > n, TakeDrop[#, UpTo[n]], {#}] &, #], 1] &, lst]

A function to group sublists of lst to be of total length as large as possible but less than or equal to n is

group[lst_, n_] := Flatten[Rest@Quiet@Reap[NestWhile[(m = 1; While[f[#, m] <= n, m++]; 
    l = TakeDrop[#, m - 1]; Sow[First[l]]; Last[l]) &, lst, # != {} &]], 2]

with

f[lst_, n_] := Tr[Length[#] & /@ Take[lst, n]]

Then,

group[inlist, 10]
(* {{{"a", "b", "c", "d", "e"}, {" "}, {"f", "g", "h"}}, {{"i", "j", "k", "l"}, 
     {"m", "n", "o", "p"}}} *)

group[limlen[inlist2, 10], 10]
(* {{{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}}, {{"k", "l"}, 
     {"m", "n", "o", "p"}}} *)

as desired.

Answer 3

Update

Per a comment by the OP, here's an updated version that manages sublists of length larger than 10 in the following way. If needed, the first chunk of the offending sublist is appended to the current list to get that list up to a total Flattened length of 10. The rest of the list is partitioned into lists of length 10 plus a list of length the remainder upon division by 10. This last list is then the first sublist used in the next set of sublists.

Here is the klugey, pretty-ugly code. Given time later, I might take a crack at simplifying some of the klugey bits (like that explicit CompoundExpression and everything associated with it).

partitionByLength[inlist_, len_] := Module[{lst},
  Append[#2[[1]], #1] & @@ Reap@Fold[
     Which[
       Length@Flatten@(lst = Append[#1, #2]) <= len
       , lst
       , Length[#2] <= len
       , Sow[#1]; {#2}
       , True
       , Sow[Append[#1, #2[[;; len - Length@Flatten@#1]]]]
       ; CompoundExpression @@ {Sow /@ List /@ Most@#, {Last@#}} &@
          Internal`PartitionRagged[
           #
           , Append[
              ConstantArray[len, Quotient[Length@#, len]]
              , Mod[Length@#, len]
             ]
           ] &@Flatten[lst][[len + 1 ;;]]
       ] &
     , {}
     , inlist]
  ] //. {} :> (##[]&)

Usage:

partitionByLength[inlist, 10]
(* (* {{{"a", "b", "c", "d", "e"}, {" "}, {"f", "g", "h"}}, {{"i", "j", "k", "l"}, {"m", "n", "o", "p"}}} *)

lst = {Range[6], Range[10], Range[2]}
partitionByLength[lst, 4]
(* {{{1, 2, 3, 4}}, {{5, 6}, {1, 2}}, {{3, 4, 5, 6}}, {{7, 8, 9, 10}}, {{1, 2}}} *)

Original post

Here's something that seems to work. It's not well tested (perhaps you can add some other examples?) and it's probably slow, but here goes:

partition10[inlist_] := First@Last@Reap@Fold[
    If[
      Tr[Length /@ (lst = Append[#1, #2])] <= 10
       , lst
       , Sow[#1]; {#2}
      ] &
     , {}
     , Append[inlist, Range[11]]
    ]
inlist = {{"a", "b", "c", "d", "e"}, {" "}, {"f", "g", "h"}, {"i", "j", "k", "l"}, {"m", "n", "o", "p"}};
partition10[inlist]
(* {{{"a", "b", "c", "d", "e"}, {" "}, {"f", "g", "h"}}, {{"i", "j", "k", "l"}, {"m", "n", "o", "p"}}} *)

For the lists that have sublists of length greater than 10, my method requires pre-processing of the list, and so I cannot treat that case until I know how theses sublists of length greater than 10 can be treated (see my comment on the original post).