http://qs321.pair.com?node_id=546444


in reply to puzzle: how many ways to make $100

This is just a variation on partitions where the size of the parts is restricted to a finite set of values. I've adapted some partition code that I had lying around:
#! /usr/bin/perl -w use strict; my @parts = (100, 50, 20, 10, 5, 1); sub partitions { my $n = shift; return partmax($n, $n) }; sub partmax { my ($n, $maxpart) = @_; return [] if $n < 0; return [[]] if $n == 0; my $partitions = []; foreach my $part (grep {$_<=$maxpart} @parts) { my $subpartitions = partmax($n - $part, $part); foreach (@$subpartitions) { unshift @$_, $part; } push @$partitions, @$subpartitions; } return $partitions; } my $example = partitions shift; print "count: ", scalar @$example, "\n"; foreach my $partition (@$example) { print join(" ", @$partition), "\n"; }