Summing Subsets

So, the third challenge was to count the number of subsets of a set of numbers such that the largest number in the subset is the sum of the rest of the numbers in the subset. My first attempt was very straightforward: create all the subsets and check to see if they have the desired property:

my @a = 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92,
 95, 97, 99;

my $hits = 0;

for 1..(2 ** +@a) -> $key {
    my @b = gather for 0..+@a -> $i { take @a[$i] if $key +& (2 ** $i); }
    my $test = @b.pop;
    next if $test != [+] @b;
    $hits++;
    say (@b, $test).join(' ');
}

say "$hits hits";

I think this works correctly, but it will be a long time before we know — as I type this, it’s been running for ten hours on my fastest computer, and I don’t anticipate it finishing any time soon.

My second attempt relies on recursion, the fact the list is sorted, and skipping fruitless branches to get the job done much faster — 47 seconds, to be precise.

sub CountSumSets($target, @a) {
    my $sets = 0;
    for ^ +@a -> $i {
        if @a[$i] < $target {
            $sets += CountSumSets($target - @a[$i], @a[($i + 1) .. (@a - 1)]);
        } elsif @a[$i] == $target {
            $sets += 1;
        }
    }
    $sets;
}


my @a = 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99;
@a .= reverse;

my $hits = 0;

for ^ +@a -> $i {
    $hits += CountSumSets(@a[$i], @a[($i + 1) .. (@a - 1)]);
}

say $hits;
About these ads

6 Responses to “Summing Subsets”

  1. roy_hu Says:

    You could use dynamic programming to solve this problem instantly. To start, build a 2D-table in which the rows represent the source set, and the columns represent sum targets between 3 and 99.

    • colomon Says:

      Would you care to provide an implementation? This sounds like an interesting and useful way of solving the problem.

      • Tim Bollman Says:

        This should do the trick:
        my @a = 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99;
        my @counts = 0 xx 100;
        for @a -> $a
        {
        for reverse $a .. 100 -> $b
        {
        if @counts[$b - $a] != 0
        {
        @counts[$b] += @counts[$b - $a];
        }
        }
        @counts[$a]++;
        }
        say [+] (-@a.elems, @counts[@a]);

      • Tim Bollman Says:

        For the explanation of how that works in more abstract terms than what I do:
        1. We start with an array of how many ways we can get to a particular number given all the numbers smaller than the current one.
        2. We add the current number to all numbers that could previously be reached to get the list of all numbers that can be reached using the current number and any of the previous numbers.
        3. Pairwise add the list of previous counts to the ways we can get to numbers using the current number.
        4. Step to the next number in our master set until exhausted.
        5. sum up all the counts. Subtract out the number of elements in the master set because our count set contains the 1 element subsets which aren’t allowed in the problem.
        My program merges steps 2 and 3 because as long as you go from the big numbers to the small numbers, you don’t need to keep track of the old counts. And messes up step 2 a little because I should have initialized @count as (1, 0 xx 99) so I could remove the @counts[$a]++. Also the .. 100 should be .. 99.

      • Tim Bollman Says:

        Shorter version that doesn’t reuse the count array but would theoretically have multi-threading. There’s no requirement that @a be presorted:
        my @a = …
        my $biggest = @a.max
        my @counts = (1, 0 xx $biggest)
        @counts = @counts >>+<< (0 xx $_, @counts[0 .. $biggest - $_]) for @a
        [+] (-@a.elems, @counts[@a])

      • roy_hu Says:

        I uploaded my Haskell code to http://gist.github.com/625639 I know no perl.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: