use warnings;
use strict;

use Data::Dumper;

# nCk - combinatoric n Choose k (binomial coefficients)
sub nck (&&$@) {
    my $end_cond   = shift();
    my $nextk_cond = shift();
    my $k          = shift();

    return () unless defined($k);

    # start recursive grouping when end condition is fulfilled
    return [] if $end_cond->($k);

    # keep looking for a partner
    my @groups;
    while (@_)
    {
        # nextk condition can force early exit by returning undef
        my $pick = shift();
        push @groups,
            map { unshift(@{ $_ }, $pick); $_ }
            &nck($end_cond, $nextk_cond, $nextk_cond->($k, $pick), @_)
+;
    }

    return @groups;
}

# grab data
my @data;
push(@data, [ map { int $_ } split ]) while <DATA>;

#print Dumper(\@data);

# total transations cost between both groups
sub get_cost {
    my @pick;
    ++$pick[$_] for @_;

    my $cost = 0;

    for my $j (0 .. 7)
    {
        next if $pick[$j];

        for my $i (@_)
        {
            $cost += $data[$i][$j];
        }
    }

    return $cost;
}

# standard 8 choose 4 == 8!/(4! * 4!) == 70 combinations
my @group_cost =
    sort { $a->[1] <=> $b->[1] }
    map { [ $_, get_cost(@{ $_ }) ] }
    nck(sub { $_[0] <= 0 }, sub { $_[0] - 1 }, 4, 0 .. 7);

#print Dumper(\@group_cost);

print "Lowest cost ($group_cost[0][1]) groups are:\n\n";
print Dumper($group_cost[0][0], $group_cost[1][0]);

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