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 meditating upon the Monastery: (8)
As of 2015-07-29 08:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (261 votes), past polls