Re: 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 );
[download]

Output

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

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;

Comment on Re: partition of an array Select or Download Code

Replies are listed 'Best First'.
Re^2: partition of an array by Corion (Patriarch) 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/;` [download] In this example, the greedy approach will fail, producing `[4,2,2,1], [2,2,1,1]` [download] while the best solution would be `[4,1,1,1], [2,2,2,2]` [download] But due to the homeworky nature of the problem I won't go into this further :)	[reply] [d/l] [select]
Re^3: partition of an array by f00li5h (Chaplain) on Mar 25, 2009 at 06:44 UTC
Does not. Output: `$VAR1 = [ '1', '1', '2', '2' ]; $VAR2 = [ '1', '2', '2', '4' ]; we have 6 and 9` [download] 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;`	[reply] [d/l] [select]