Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Comment on

( #3333=superdoc: 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' ] ];

In reply to Re: How can I calculate the right combination of postage stamps? (combinatoric n Choose k with conditions) by repellent
in thread How can I calculate the right combination of postage stamps? by brian_d_foy

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others taking refuge in the Monastery: (4)
    As of 2014-07-26 20:21 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My favorite superfluous repetitious redundant duplicative phrase is:









      Results (179 votes), past polls