Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
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??


in reply to How can I calculate the right combination of postage stamps?

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)
Select or Download Code

Log In?
Username:
Password:

What's my password?
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?
Others taking refuge in the Monastery: (5)
As of 2014-07-23 04:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (133 votes), past polls