The stupid question is the question not asked PerlMonks

### Re: How can I calculate the right combination of postage stamps? (combinatoric n Choose k with conditions)

by repellent (Priest)
 on Dec 01, 2008 at 19:08 UTC ( #727191=note: print w/replies, xml ) Need Help??

brian_d_foy,

You can try traversing the collection of stamps in a combinatoric n-choose-k fashion (see Math::Combinatorics's combine()), 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 :)

UPDATE: Here it is in Perl.

```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'
]
];
• Comment on Re: How can I calculate the right combination of postage stamps? (combinatoric n Choose k with conditions)

Create A New User
Node Status?
node history
Node Type: note [id://727191]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
As of 2020-02-27 00:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What numbers are you going to focus on primarily in 2020?

Results (117 votes). Check out past polls.

Notices?