Re: "Divide" challenge

moritz is right, brute forcing this is straightforward, unless we've completely misunderstood the challenge. Here's my code which, with the data you gave, finds the split to be groups 0, 1, 4, 6 and 2, 3, 5, 7. (Machine numbers starting with zero).

use strict;
use warnings;

my @costs;
push @costs, [split(/\s+/)] for (<DATA>);

my @combos;
gen_set([0..7],[],4,\@combos);
my $min_cost = 999999;
my $min_set_num;

for (0..$#combos) {
    my $set_cost = get_cost(@{$combos[$_]});
    if ($set_cost < $min_cost) {
        $min_cost = $set_cost;
        $min_set_num = $_;
    }
}

print "Set number $min_set_num, cost $min_cost: ".
  join(q{ },@{$combos[$min_set_num]}) . "\n";

sub get_cost {
    my @list = @_;
    my %list = map { $_ => 1 } @list;
    my $cost;
    for my $li (@list) {
        for my $oi (grep {not exists $list{$_}} (0..7)) {
            $cost += $costs[$li]->[$oi];
        }
    }
    return $cost;
}

sub gen_set {
    my ($from, $to, $num, $results) = @_;
    for my $item (@$from) {
        my @new_to = @$to;
        push @new_to, $item;
        if ($num == 1) {
            push @$results, \@new_to;
        } else {
            my @new_from = grep { $_ != $item } @$from;
            gen_set(\@new_from,\@new_to,$num-1,$results);
        }
    }
}


__DATA__
-  38 72 79 58 88 59 33
38 -  70 71 27 47 77 14
72 70 -  90 42 63 56 90
79 71 90 -  60 57 21 95
58 27 42 60 -  28 33 52
88 47 63 57 28 -  11 85
59 77 56 21 33 11 -  59
33 14 90 95 52 85 59 -
[download]

Comment on Re: "Divide" challenge Download Code

Replies are listed 'Best First'.
Re^2: "Divide" challenge by ELISHEVA (Prior) on Mar 10, 2009 at 17:58 UTC
Brute forcing is not quite as straight forward as one might think :-) The solution above is working a lot harder than is really necessary, even for a brute force solution. If I understand the problem correctly, we are trying to minimize the data exchanged between the groups. Therefore what matters is the sum of data exchanged between the two groups, not the internal composition of each group. This lets us significantly reduce the potential solution space. The combination generator above generates every single permutation of 4 elements drawn from 8, not just every single combination. For example, this is the list of combinations produced by `gen_set([0..3],[],2, \@combos);`. There are 12 items, but if we disregard order only 6 would count. `<0 1> <0 2> <0 3> <1 0> <1 2> <1 3> <2 0> <2 1> <2 3> <3 0> <3 1> <3 2>` [download] In actual fact, though we need only half of the combinations, even after ignoring order. This is because our second bag is always the complement of our first bag. Since sums are commutative, trying out the division (bag 1, complement of bag 1) is going to result in the exact same data flow sum as the division (complement of bag 1, bag 1) Best, beth	[reply] [d/l] [select]
Re^3: "Divide" challenge by bellaire (Hermit) on Mar 10, 2009 at 18:11 UTC
Thanks, beth, I'll ++ tomorrow when I have more votes. :) This was definitely working harder than necessary to obtain a solution, and no attempt was made at optimization. However, even doing things the "dumb" way, the whole operation still runs in the blink of an eye, which detracts from the OP's assertion that this would be a difficult problem to brute force, in principle.	[reply]
Re^3: "Divide" challenge by repellent (Priest) on Mar 12, 2009 at 21:53 UTC
Hmmm... I wonder why moritz mentioned 8! / (4! * 2!) == 840 possibilities, when we only need to traverse 8! / 2 * (4! * 4!) == 35 possibilities at minimum. Am I missing something? Read more... (2 kB) Output: `Lowest cost (803) groups are: $VAR1 = [ 0, 1, 4, 6 ]; $VAR2 = [ 2, 3, 5, 7 ];` [download]	[reply] [d/l] [select]