Re^6: Divide array of integers into most similar value halves

It's obviously not the best algorithm, and I rushed the implementation.

use strict;
use warnings;

use Algorithm::Loops qw( NextPermuteNum );
use List::Util       qw( sum );

my @nums = @ARGV;

my $sum  = sum @nums;
my @best = @nums;
my $best;
@nums = sort { $a <=> $b } @nums;
do {
   my $p = $sum;
   my $q = 0;
   for my $i (0..$#nums) {
      my $x = $nums[$i];
      $p -= $x;
      $q += $x;
      my $diff = abs($p-$q);
      if (!defined($best) || $best > $diff) {
         $best = $diff;
         @best = (
            [ @nums[ 0    .. $i     ] ],
            [ @nums[ $i+1 .. $#nums ] ],
         );
      }
   }
} while ( NextPermuteNum(@nums) );

my @p = @{ $best[0] };  print(sum(@p), ": ", join('+', @p), "\n");
my @q = @{ $best[1] };  print(sum(@q), ": ", join('+', @q), "\n");
[download]

>perl script.pl 8 14 32 29
40: 8+32
43: 14+29

>perl script.pl 7 10 12 15 40
44: 7+10+12+15
40: 40
[download]

I'm not clear on the complexity of NextPermuteNum — I have a cold that is making me very tired — so maybe my analysis is wrong.

Comment on Re^6: Divide array of integers into most similar value halves Select or Download Code

Replies are listed 'Best First'.
Re^7: Divide array of integers into most similar value halves by moritz (Cardinal) on Sep 01, 2008 at 20:50 UTC
The number of permutations is actually `n!`, which is why your algorithm doesn't run in polynomial time: `$ time perl foo2.pl 1 2 3 4 5 6 7 14: 1+2+4+7 14: 3+5+6 real 0m0.096s time perl foo2.pl 1 2 3 4 5 6 7 8 18: 1+2+3+4+8 18: 5+6+7 real 0m0.590s time perl foo2.pl 1 2 3 4 5 6 7 8 9 22: 1+2+3+4+5+7 23: 6+8+9 real 0m5.766s $ time perl foo2.pl 1 2 3 4 5 6 7 8 9 10 28: 1+2+3+4+5+6+7 27: 8+9+10 real 0m57.315s $ time perl foo2.pl 1 2 3 4 5 6 7 8 9 10 11 33: 1+2+3+4+5+7+11 33: 6+8+9+10 real 11m5.687s` [download] You can see that there's a (very rough) factor of 10 between each of these runs, which indicates exponential growth. (Update: added result of last calculation; Second Update: I had some stupid copy&paste errors in the data, which Hue-Bond++ was so friendly to point out. Fixed)	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^7: Divide array of integers into most similar value halves
by moritz (Cardinal) on Sep 01, 2008 at 20:50 UTC

n!

$ time perl foo2.pl 1 2 3 4 5 6 7
14: 1+2+4+7
14: 3+5+6

real    0m0.096s

time perl foo2.pl 1 2 3 4 5 6 7 8
18: 1+2+3+4+8
18: 5+6+7

real    0m0.590s


time perl foo2.pl 1 2 3 4 5 6 7 8 9
22: 1+2+3+4+5+7
23: 6+8+9

real    0m5.766s

$ time perl foo2.pl 1 2 3 4 5 6 7 8 9 10
28: 1+2+3+4+5+6+7
27: 8+9+10

real    0m57.315s

$ time perl foo2.pl 1 2 3 4 5 6 7 8 9 10 11 
33: 1+2+3+4+5+7+11
33: 6+8+9+10

real    11m5.687s
[download]

You can see that there's a (very rough) factor of 10 between each of these runs, which indicates exponential growth.

(Update: added result of last calculation; Second Update: I had some stupid copy&paste errors in the data, which Hue-Bond++ was so friendly to point out. Fixed)

[reply]
[d/l]
[select]