4
$\begingroup$

I'm having quite a hard time with the following. I would like to partition a list into a list of sub-lists, in such a way that the number n of sub-lists is fixed.

For example, suppose I'm looking for a partition of size n=3:

L = {1,2,3,4,5};
n = 3;

size = Ceiling[Length[L]/n]
Partition[L, size, size, {1,1}, {}]

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

Great! But now I run into problems when n=4. Namely, the above method produces the same length 3 output. This is basically due to exhaustion of the original list L.

My solution so far is to use an ad hoc if statement that takes an element from the first bucket:

L = {1,2,3,4,5};
n = 4;

size = Ceiling[Length[L]/n]
newL = Partition[L, size, size, {1, 1}, {}]

If[Length[newL] < n,
 AppendTo[newL, {newL[[1, 1]]}];
 newL[[1]] = newL[[1, 2 ;;]];
];

newL 

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

Is there a better way to do this?

Edit 1:

kguler's answer was great, but Kellen's solution definitely performs better for large inputs: (blue = kguler's bpF2, red = Kellen's splitup)

enter image description here

Thanks guys!

Edit 2:

I answered my own question below, because I found a nice one-liner solution which also improves performance.

$\endgroup$
  • 1
    $\begingroup$ How big are these parts supposed to be? Many easy ways to do this would be to simply pick a relatively small number p of parts, so that p(k-1)<n and then just pick out the first k-1 parts to be of size p, and throw everything into the last part. My answer will assume that you want parts of nearly-equal (off by one) size. $\endgroup$ – Kellen Myers Nov 28 '14 at 23:58
7
$\begingroup$

If you have your set of size n, and you want to partition that set into k parts as fairly as possible (into a sets of size s and b of s+1) then you have: $$n=as+b(s+1)=(a+b)s+b=ks+b$$

So b=Mod[n,k] (and of course a=k-b). You also have s=Quotient[n,k]. Then you just make use of the existing partition function:

n = 5; k = 4;
lst=Range[n];
b = Mod[n, k];
a = k - b;
s = Quotient[n, k];
small = Take[Partition[lst, s], a];
big = Partition[Drop[lst, a s], s + 1];
Join[small, big]

Or, if you want to pack this into a one-liner:

splitup[L_, k_] :=
 Join[
  Take[Partition[L, Quotient[Length[L], k]], k - Mod[Length[L], k]],
  Partition[Drop[L, (k - Mod[Length[L], k]) Quotient[Length[L], k]],
    Quotient[Length[L], k] + 1]
  ]

That works for any list L and any number of parts k.

Edit: In retrospect I realize I've changed your "n" to be my "k." I think "n" looks better as the size of the list and "k" as the number of parts in the partition. Sorry if that gets anybody confused.

$\endgroup$
  • $\begingroup$ I like this. You're sure to get a balanced partition this way. $\endgroup$ – Kris Nov 30 '14 at 19:32
  • $\begingroup$ Anybody want to explain the downvotes here? $\endgroup$ – Kellen Myers Jan 3 '15 at 22:00
4
$\begingroup$
bpF = Internal`PartitionRagged[Range[#], IntegerPartitions[#, {#2}, Quotient[#, #2] + {0, 1}]] &;

bpF[5, 4]
(* {{1, 2}, {3}, {4}, {5}} *)

bpF[10,6]
(*  {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9}, {10}}  *)

or

bpF2 = Internal`PartitionRagged[#, 
          IntegerPartitions[Length@#, {#2}, Quotient[Length@#, #2] + {0, 1}]] &;

bpF2[Range@5, 4]
(* {{1,2},{3},{4},{5}} *)

bpF2[Range@10, 6]
(* {{1,2},{3,4},{5,6},{7,8},{9},{10}} *)
$\endgroup$
  • $\begingroup$ Very nice! I like that there's a one-liner for this. I am a bit worried about the IntegerPartitions call when it comes to performance, though. $\endgroup$ – Kris Nov 30 '14 at 20:05
3
$\begingroup$

It might be a bit unusual, but I'm answering my own question because I just found a very nice solution using the built-in function Multicolumn:

BinBalanced[list_, n_] := DeleteCases[#, ""] & /@ Normal@Multicolumn[list, {n, Automatic}]

BinBalanced[{1, 2, 3, 4, 5}, 4]

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

This slightly improves performance on average, compared to Kellen's splitup.

$\endgroup$
1
$\begingroup$

This is one of the ways:

lst = Range[5];
n = 4;
n0 = Floor[Length[lst]/n];
res = Partition[Take[lst, n n0], n0];
res[[-1]] = Join[res[[-1]], Drop[lst, n n0]];
res

(* {{1}, {2}, {3}, {4, 5}} *

$\endgroup$
  • $\begingroup$ For different parameter values, you could be lumping in an arbitrarily large number of "leftovers" into the last part of res. Is that really what you intend? $\endgroup$ – Kellen Myers Nov 29 '14 at 18:12
  • $\begingroup$ @Kellen Yes, I realized that the last sublist could be rather much longer than the others. Obviously, the number of "leftovers" is at most n-1. I had some other solutions that resulted in sublists of almost the same length, as in your solution, but they did not maintain the order of the elements of the original list, Yours does, so I prefer yours. $\endgroup$ – Fred Simons Nov 29 '14 at 20:12
  • $\begingroup$ @Kellen Just in case you are interested here is another onliner for a given list lst and number of sublists n, but is does not maintain the original ordering: With[{aux = Transpose[{Range[Length[lst]], lst}]}, Map[Last, GatherBy[aux, Mod[#[[1]], n] &], {2}]] $\endgroup$ – Fred Simons Nov 29 '14 at 20:28

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.