1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl
#
# .pl
#
# Tug of War
# Submitted by: Mohammad S Anwar
# You are given a set of $n integers (n1, n2, n3, ….).
#
# Write a script to divide the set in two subsets of n/2 sizes each so
# that the difference of the sum of two subsets is the least. If $n is
# even then each subset must be of size $n/2 each. In case $n is odd
# then one subset must be ($n-1)/2 and other must be ($n+1)/2.
#
# Example
#
# Input: Set = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
# Output: Subset 1 = (30, 40, 60, 70, 80)
# Subset 2 = (10, 20, 50, 90, 100)
#
# Input: Set = (10, -15, 20, 30, -25, 0, 5, 40, -5)
# Subset 1 = (30, 0, 5, -5) = 30
# Subset 2 = (10, -15, 20, -25, 40) = 30
#
# method:
# Did we do something like this already? In any case an algorithm
# springs immediately to mind: sort the input, and distribute the two
# largest values betwen the other lists.
# Yea, but negative values complicate that algorithm, especially when it
# comes to making sure the divided parts are of equal-ish size. After
# exploring that angle, I decided it was too complicated. So rather than
# that, we're going to exhaustively compute the combinations n choose k
# for half the elements, rounding down. Subtracting the sum of the
# combination from the total sum of the list gives the fitness metric to
# be minimized.
#
# Actually the difference of the part versus half the total will be the
# same for the other half, so we can construct the metric by doubling
# the partial sum and subtracting that, which is easier. We keep a
# running minimum, keeping the difference between the segments and the
# top-rated combination.
#
# At the end we need to create the complement segment, which we do by
# finding the index of and then splicing out the elements in the
# minimizing combination from the original inoput list.
#
# © 2021 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use List::Util qw( sum first );
use Algorithm::Combinatorics qw( combinations );
my @input = sort { $a <=> $b } @ARGV > 0
? @ARGV
: (10, -15, 20, 30, -25, 0, 5, 40, -5);
die "must have more than 1 element in input array" if @input < 2;
my $sum = my $min = sum( @input );
my @part1;
my $half = int( @input/2 );
my $iter = combinations(\@input, $half);
while (my $c = $iter->next) {
my $partial = sum $c->@*;
if (abs($sum - 2 * $partial) < $min) {
$min = abs($sum - 2 * $partial);
@part1 = $c->@*;
}
}
for my $target ( @part1 ) {
splice @input, (first { $input[$_] == $target } (0..$#input)), 1;
}
my $output =
(join ' + ', sort {$b<=>$a} @part1) . ' = ' . sum( @part1 ) . "\n"
. (join ' + ', sort {$b<=>$a} @input) . ' = ' . sum( @input );
$output =~ s/\+ \-/- /g;
say $output;
|
