TL;DR

On with TASK #2 from The Weekly Challenge #124. Enjoy!

The challenge

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)
Output:  Subset 1 = (30, 0, 5, -5)
         Subset 2 = (10, -15, 20, -25, 40)

The questions

Just as a curiosity, I’d ask if it’s a real set or something like a multiset, where items might be repeated. I’ll assume it’s a set, which will come handy in the Raku solution, but the whole thing can be rearranged to cope with multisets as well (as an example, the Perl solution does not care about it).

The solution

I was really in a hurry this time and I only got to implement the dumbest of the algorithms: try all possible partitions of the input set into two “halves” according to the rules, and keep the one with the best score.

The condition we’re using here is that the sum of only one of the two subsets is as close as possible to the half of the sum of all elements. This allows us to spare one sum at each iteration through the possible combinations.

Due to the hurry, I started from Perl first, leveraging the Combinations iterator:

sub tug_of_war (@set) {
   my $n = scalar @set; # number of elements in the set
   my $n_2 = $n % 2 ? ($n - 1) / 2 : $n / 2; # size of "smaller" subset
   my $subset_target = sum(@set) / 2;        # target "half" of sum

   # we will go through the possible combinations of $n_2 elements out
   # of our $n in the @set, checking their sum against the "subset target"
   # of one-half of the total sum
   my $cit = combinations_iterator($n_2, @set);

   # this will keep our "best" rolling solution during the iteration, and
   # the absolute best at the end
   my ($solution, $solution_delta);
   while (my @subsets = $cit->()) {
      # our combinations_iterator returns both the $n_2 subset, as well as
      # the remaining items. We will concentrate the sum on the first
      # sub-array, i.e. the first subset

      # we evaluate how far we are from the target sum for a subset. We
      # don't care about the sign, just "how much" we're far off
      my $subset_delta = abs(sum($subsets[0]->@*) - $subset_target);

      # update our current best according to the new combination. This also
      # takes care of the initialization at the first pass, thanks to the
      # check for !$solution
      ($solution, $solution_delta) = (\@subsets, $subset_delta)
         if (!$solution) || ($solution_delta > $subset_delta);

      # if we're below the tolerance for our distance to the target, let's
      # call it a day and return this solution!
      last if $subset_delta < TOLERANCE;
   }
   return $solution->@*;
}

The Raku version is an attempt to a translation. We leverage the “batteries included” combinations routine here, which does not return a partition but just the combination, so we have to eventually calculate the other half of the set by using the set difference operator (-). This is where the difference between sets and multisets kicks in, so as anticipated it might be easily addressed by doing this calculation using Bags instead.

sub tug-of-war (@set) {
   my $n = @set.elems; # number of elements in the set
   my $n_2 = $n %% 2 ?? $n / 2 !! ($n - 1) / 2; # size of "smaller" subset
   my $subset_target = @set.sum / 2;            # target "half" of sum
   my (@solution, $solution_delta);
   for @set.combinations($n_2) -> @subset {
      my $subset_delta = abs(@subset.sum - $subset_target);
      ($solution_delta, @solution) = ($subset_delta, |@subset)
         if (!defined($solution_delta)) || ($solution_delta > $subset_delta);
      last if $solution_delta < TOLERANCE;
   }
   return (@solution, (@set (-) @solution).keys);
}

The full code will be available soon in The Weekly Challenge repository, for now… have fun and stay safe!!!