breaking an array into nearly equal parts

[santonegro]

I want to take an array consisting of X elements and break it into 3 equal sized arrays if possible. if this is not possible, then I want a few arrays with slightly more elements. here is a sample table:

number elements in array	/3	%3	size of each array
6	2	0	2,2,2
7	2	1	3,2,2
8	2	2	3,3,2
9	3	0	3,3,3
10	3	1	4,3,3
11	3	2	4,4,3
12	4	0	4,4,4
13	4	1	5,4,4
14	4	2	5,5,4
15	5	0	5,5,5

[revdiablo]

Did you notice a pattern in the table you pasted? It looks like it contains all the information you need. It's basically like this:

If $x%3 is 0, the arrays should all be of size $x/3. If $x%3 is not 0, there should be $x-($x%3) arrays of size $x/3 and $x%3 of size $x/3+1.

I'm not positive this will continue to hold true, but it looks good from what you've shown. There may be a simpler algorithm too, so I would be happy to see other replies. :-)

[spiritway]

You're right - and the pattern holds true. A positive integer can either be exactly divisible by three, have a remainder of 1, or a remainder of 2. Your idea is probably one of the simplest.

[Roy Johnson]

It is quite simple. Here's an implementation. The apportion figures out chunk sizes; multi_slice returns slices of those sizes. The for block runs a few examples.

sub apportion {
  my ($elements, $pieces) = @_;
  my $small_chunk = int $elements / $pieces;
  my $oversized_count = $elements % $pieces;
  ((1 + $small_chunk) x ($oversized_count), ($small_chunk) x ($pieces 
+- $oversized_count));
}

sub multi_slice {
  my ($aref, @chunk_sizes) = @_;
  my $hi_i = -1;
  map {
    my $lo_i = $hi_i + 1;
    $hi_i += $_;
    [@$aref[$lo_i..$hi_i]]
  } @chunk_sizes;
}

for my $try ([16,3], [17,4], [19,3]) {
  print "$try->[0] elements into $try->[1] pieces:\n";
  print "Sizes: ", join(', ', apportion(@$try)), "\n";
  print "@$_\n" for multi_slice([1..$try->[0]], apportion(@$try));
}

[davido]

You can use math and slices if you want...

use strict;
use warnings;
use Data::Dumper;


my @array = ( 0 .. 12 );

my @newarray;

@newarray[ 0 .. 2 ] = ( 
                  [ @array[ 0 .. $#array * .333 ]                 ],
                  [ @array[ $#array * .333 + 1 .. $#array * .667] ],
                  [ @array[ $#array * .667 + 1 .. $#array ]       ] 
);

print Dumper @newarray;

This will keep the sub-arrays balanced to within one element of each other in size.

[TedPride]

Another interesting way to do it:

use strict;
use warnings;

my @orig = 1..17;
my $arrs = 4;

my @arrs;      ##### And here we go: #####
push @{$arrs[$_ % $arrs]}, $orig[$_] for 0..$#orig;

print join ' ', @$_, "\n" for @arrs;

[Mandrake]

This works for me.


#!/usr/bin/perl -w
use strict;

my @arr = (1..15) ;
my ($offset,$offset1) ;
$offset = $offset1 = int((scalar @arr)/3);

$offset++ if (scalar @arr % 3 > 0) ;
$offset1++  if (scalar @arr % 3 > 1) ;

my ($arr1, $arr2, $arr3) =
([@arr[0..$offset-1]],[@arr[$offset..$offset+$offset1-1]],[@arr[$offse
+t+$offset1..scalar @arr -1]]);

print $_."\n"  for ((@$arr1,("\n"),@$arr2),("\n"),@$arr3);

A bit lengthy but you can try refactoring it.

[nicoaimetti]

Another one...

#!/usr/bin/perl -w

use strict;

my @A= 1..int(rand(21));
print "\@A: ",scalar @A,$/;

my @parts;
$parts[3-$_] = [splice @A,0, @A%$_?int(@A/$_)+1:int(@A/$_)] foreach (r
+everse 1..3); #@A is empty now.

print join( ' ',@$_)," : ",scalar @$_,$/ for @parts;

But I prefer the one posted by TedPride.

[nicoaimetti]

Simple improvement...

$parts[$n-$_] = [splice @A, 0, (@A/$_)+(@A%$_&&1)] for reverse 1..$n;