Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
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;


Comment on Re: partition of an array
Select or Download Code
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;

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://749216]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (8)
As of 2015-07-07 06:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (87 votes), past polls