Perl-Sensitive Sunglasses PerlMonks

### Re: How to generate restricted partitions of an integer

by tye (Sage)
 on Nov 12, 2004 at 09:11 UTC ( #407313=note: print w/replies, xml ) Need Help??

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)
>

- tye

Create A New User
Node Status?
node history
Node Type: note [id://407313]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (7)
As of 2020-10-20 21:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite web site is:

Results (210 votes). Check out past polls.

Notices?