Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

Re: How to generate restricted partitions of an integer

by Roy Johnson (Monsignor)
on Nov 11, 2004 at 16:02 UTC ( #407083=note: print w/replies, xml ) Need Help??

in reply to How to generate restricted partitions of an integer

I would do it recursively:
use warnings; @denoms = qw(2 5 10 20 50 100); sub change { my ($unchanged, $nothing_smaller_than) = (@_,0); my @results = (); for my $trybill (@denoms) { next if ($trybill < $nothing_smaller_than); if ($trybill < $unchanged) { my $remaining = $unchanged - $trybill; push @results, map {[$trybill, @$_]} change($remaining, $trybill +); } elsif ($trybill == $unchanged) { push @results, [$trybill]; } else { last } } return @results; } use Data::Dumper; print Dumper change(100);
Try each denomination against what is to be changed. If the bill being tried ($trybill) is less than the amount to be changed ($unchanged), then make a result set out of $trybill mapped to each combination returned by change($unchanged-$trybill).

The $nothing_smaller_than parameter ensures that the output doesn't result in multiple permutations of the same combination of bills: only the canonical order of smallest bill to largest bill will be returned.

Caution: Contents may have been coded under pressure.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://407083]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2020-10-20 20:19 GMT
Find Nodes?
    Voting Booth?
    My favourite web site is:

    Results (210 votes). Check out past polls.