go ahead... be a heretic 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?
 [stevieb]: Playing around with two DACs to control a single RGB LED (each DAC only has two outputs, LED has 3 inputs), and have realized that each of my IC RPi dists needs a wiring diagram, which is linked to within the documentation

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (5)
As of 2017-08-20 19:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (317 votes). Check out past polls.

Notices?