Beefy Boxes and Bandwidth Generously Provided by pair Networks
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 ( #516493=perlquestion: print w/replies, xml ) 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;

Log In?
Username:
Password:

What's my password?
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?