Re: How to generate restricted partitions of an integer

[tye]

This one takes the desired total and/or the list of denominations on the command line and shows all possible combinations:

#!/usr/bin/perl -w
use strict;
use Algorithm::Loops qw(
        NestedLoops MapCarMin );
 
my @sum= shift || 100;
my @size= ( 100, 50, 20, 10, 5 );
@size= @ARGV   if  @ARGV;
my $tries= 0;
my $iter= NestedLoops(
    [ ( sub {
            my $n= $sum[@_]/$size[@_];
            ! $n        ? [] :
            @_ < $#size ? [ 0 .. $n ]
                        : [ $n .. int $n ];
    } ) x @size ],
    {
        OnlyWhen => sub {
            $tries++;
            not $sum[@_]=
                $sum[$#_] - $_[-1]*$size[$#_];
        },
    },
);
my @cnt;
my $seq= 0;
while(  @cnt= $iter->()  ) {
    printf "%d) %s\n", ++$seq, join ' + ',
        MapCarMin {
            !$_[0] ? () : join '*', @_
        } \@cnt, \@size;
}
print "($tries tries)\n";

And here's a sample run:

> perl change.pl 103 100 33 10 3 | more
1) 1*10 + 31*3
2) 4*10 + 21*3
3) 7*10 + 11*3
4) 10*10 + 1*3
5) 1*33 + 1*10 + 20*3
6) 1*33 + 4*10 + 10*3
7) 1*33 + 7*10
8) 2*33 + 1*10 + 9*3
9) 1*100 + 1*3
(56 tries)
>