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.


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"}}}
  • $\begingroup$ Does the order of elements remain fixed, that is, is Flatten@result==Flatten@source to be true? $\endgroup$
    – ciao
    Dec 28 '15 at 2:53
  • $\begingroup$ @ciao the order should not change. $\endgroup$ Dec 28 '15 at 3:21
  • $\begingroup$ Another clarifying question: with the too-long lists, do you always split at the end of the list? i.e. take the first ten elements of the list and split of the last n elements? Or can you capture some of the first elements of the list if the previous lists don't yet add up to length 10? $\endgroup$
    – march
    Dec 28 '15 at 6:12
  • $\begingroup$ @march appending to the previous lists would be better $\endgroup$ Dec 28 '15 at 11:57

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 //

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"}}} *)

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]


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


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.



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[
       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@#}} &@
           , Append[
              ConstantArray[len, Quotient[Length@#, len]]
              , Mod[Length@#, len]
           ] &@Flatten[lst][[len + 1 ;;]]
       ] &
     , {}
     , inlist]
  ] //. {} :> (##[]&)


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[
      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"}};
(* {{{"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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.