There's more than one way to do things PerlMonks

### Re: partition of an array

by f00li5h (Chaplain)
 on Mar 09, 2009 at 06:16 UTC ( #749216=note: print w/replies, xml ) Need Help??

in reply to partition of an array

sort it and stuff the biggest one into each half...

```#! /usr/bin/perl -wT
use warnings;
use strict;

my @kitties = sort qw/ 1 2 3 4 5 9  10 /;

my \$i;
my (@first, @second);
while (@kitties){
push @first, shift @kitties;
push @second, shift @kitties;
}

use Data::Dumper;
print Dumper (\@first, \@second );

use List::Util qw[ sum ];

print "we have ", sum( @first ), " and ", sum( @second );

Output

```\$VAR1 = ['1','2','4','9'];
\$VAR2 = ['10','3','5',undef];
we have 16 and 18

this puts undefs in if there is an uneven number of elements (as this code shows)

@_=qw; ask f00li5h to appear and remain for a moment of pretend better than a lifetime;;s;;@_[map hex,split'',B204316D8C2A4516DE];;y/05/os/&print;

Replies are listed 'Best First'.
Re^2: partition of an array
by Corion (Pope) on Mar 09, 2009 at 14:08 UTC

This approach is suboptimal for the following sample case:

```my @kitties = qw/1 1 1 2 2 2 2 4/;

In this example, the greedy approach will fail, producing

```[4,2,2,1], [2,2,1,1]

while the best solution would be

```[4,1,1,1], [2,2,2,2]

But due to the homeworky nature of the problem I won't go into this further :)

Does not.

Output:

```\$VAR1 = [ '1', '1', '2', '2' ]; \$VAR2 = [ '1', '2', '2', '4' ];
we have 6 and 9

You dropped the sort bit!

... some time passes ...

Just snagging the biggest one and stuffing it in a sack works pretty well for the knapsack problem... and since this one was only 2 partitions it didn't do too bad ;)

@_=qw; ask f00li5h to appear and remain for a moment of pretend better than a lifetime;;s;;@_[map hex,split'',B204316D8C2A4516DE];;y/05/os/&print;

Create A New User
Node Status?
node history
Node Type: note [id://749216]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (2)
As of 2017-08-18 03:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (294 votes). Check out past polls.

Notices?