good chemistry is complicated,and a little bit messy -LW PerlMonks

### breaking an array into nearly equal parts

by santonegro (Scribe)
 on Dec 14, 2005 at 01:38 UTC Need Help??

santonegro has asked for the wisdom of the Perl Monks concerning the following question:

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
6202,2,2
7213,2,2
8223,3,2
9303,3,3
10314,3,3
11324,4,3
12404,4,4
13415,4,4
14425,5,4
15505,5,5

Replies are listed 'Best First'.
Re: breaking an array into nearly equal parts
by revdiablo (Prior) on Dec 14, 2005 at 02:06 UTC

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. :-)

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.

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));
}

Caution: Contents may have been coded under pressure.
Re: breaking an array into nearly equal parts
by davido (Cardinal) on Dec 14, 2005 at 02:08 UTC

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.

Dave

Re: breaking an array into nearly equal parts
by TedPride (Priest) on Dec 14, 2005 at 03:27 UTC
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;
Re: breaking an array into nearly equal parts
by Mandrake (Chaplain) on Dec 14, 2005 at 09:25 UTC
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.
Re: breaking an array into nearly equal parts
by nicoaimetti (Acolyte) on Dec 15, 2005 at 01:07 UTC
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.
Simple improvement...
```\$parts[\$n-\$_] = [splice @A, 0, (@A/\$_)+(@A%\$_&&1)] for reverse 1..\$n;

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://516493]
Approved by GrandFather
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (3)
As of 2021-12-07 02:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
R or B?

Results (33 votes). Check out past polls.

Notices?