You can try traversing the collection of stamps in a combinatoric n-choose-k fashion (see
), except that you won't be combining the stamps merely to fulfill the k-grouping criterion.
Instead, you would enforce your own criteria to guide the grouping process, while poisoning the recursion space if it ever got out-of-bounds. Think of k as a condition instead of a number.
I have a LISP-variant n-choose-k function that allows passing in conditional lambda's. Unfortunately, I don't believe there is a Perl-equivalent that does a similar thing. Good news is, it shouldn't be too hard to roll your own. Exercise left for the reader :)
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;
}
# standard 5 choose 3
my @grouping = nck sub { $_[0] <= 0 }, sub { $_[0] - 1 }, 3, qw(a b c
+d e);
# conditions set to figure out $1.51 exactly
my @stamps = (.02, .03, .04, .05, .1, .26, .27, .42, .8, .84, .87, 5)
+;
my @packing = nck sub { $_[0] >= 1.51 }, sub { my $nextk = $_[0] + $_[
+1]; $nextk <= 1.51 ? $nextk : undef }, 0, @stamps;
print Dumper(\@grouping, \@packing);
__DATA__
$VAR1 = [
[
'a',
'b',
'c'
],
[
'a',
'b',
'd'
],
[
'a',
'b',
'e'
],
[
'a',
'c',
'd'
],
[
'a',
'c',
'e'
],
[
'a',
'd',
'e'
],
[
'b',
'c',
'd'
],
[
'b',
'c',
'e'
],
[
'b',
'd',
'e'
],
[
'c',
'd',
'e'
]
];
$VAR2 = [
[
'0.02',
'0.03',
'0.04',
'0.05',
'0.26',
'0.27',
'0.84'
],
[
'0.02',
'0.04',
'0.05',
'0.26',
'0.27',
'0.87'
],
[
'0.02',
'0.27',
'0.42',
'0.8'
],
[
'0.03',
'0.04',
'0.05',
'0.1',
'0.42',
'0.87'
],
[
'0.03',
'0.05',
'0.1',
'0.26',
'0.27',
'0.8'
],
[
'0.03',
'0.26',
'0.42',
'0.8'
],
[
'0.04',
'0.1',
'0.26',
'0.27',
'0.84'
]
];
