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

[repellent]

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'
          ]
        ];