Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: partition of an array

by f00li5h (Chaplain)
on Mar 09, 2009 at 06:16 UTC ( [id://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 (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/;

    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
Domain Nodelet?
Node Status?
node history
Node Type: note [id://749216]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (4)
As of 2024-03-29 09:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found